TITLE: Sums of powers being powers of the sum
QUESTION [6 upvotes]: I'm looking for literature on solving problems of the form
$$
n_1^\alpha+\cdots+n_k^\alpha=(n_1+\cdots+n_k)^\beta
$$
for positive integers $n_1,\ldots,n_k$ and fixed parameters $k$ and $\alpha\ne\beta.$ Any ideas?
This is perhaps similar to multigrade equations or "equal sums of like powers" but not quite similar enough to use those results (as far as I can see). But surely this is too simple not to have been studied?

REPLY [1 votes]: ... Continuation:
A list of solutions for certain $(\alpha,\beta)$, $k$:
\begin{array}{|c|l|c|}
\hline
(\alpha, \beta), \; k & (n_1, \ldots, n_k) & n_1+\ldots+n_k \\
\hline \color{#003388}{(\alpha,\beta)=(4,3), \; k=1}
& \color{#CC3300}{1} & \color{#CC3300}{1} \\
\hline \color{#003388}{(\alpha,\beta)=(4,3), \; k=2}
& \color{#CC3300}{(4,4)} & \color{#CC3300}{8} \\
\hline \color{#003388}{(\alpha,\beta)=(4,3), \; k=3}
& \color{#CC3300}{(9,9,9)} & \color{#CC3300}{27} \\
\hline \color{#003388}{(\alpha,\beta)=(4,3), \; k=4}
& (7,14,14,14) & 49 \\
& \color{#CC3300}{(16,16,16,16)} & \color{#CC3300}{64} \\
\hline \color{#003388}{(\alpha,\beta)=(4,3), \; k=5}
& (5,15,15,20,20) & 75 \\
& (6,7,12,15,19) &  59 \\
& \color{#CC3300}{(25,25,25,25,25)} & \color{#CC3300}{125} \\
\hline \color{#003388}{(\alpha,\beta)=(4,3), \; k=6}
& (2,2,2,8,8,14) & 36 \\
& (2,9,14,21,22,23) & 91 \\
& (3,3,7,13,16,19) & 61 \\
& (4,5,6,11,13,20) & 59 \\
& (28,32,32,32,36,40) & 200 \\
& \color{#CC3300}{(36,36,36,36,36,36)} & \color{#CC3300}{216} \\
\hline \color{#003388}{(\alpha,\beta)=(4,3), \; k=7}
& (1,1,2,4,7,14,14) & 43 \\
& (1,2,11,14,17,20,26) & 91 \\
& (1,5,6,6,11,11,21) & 61 \\
& (1,8,12,22,23,28,29) & 123 \\
& (1,22,23,26,29,33,39) & 173 \\
& (2,2,4,12,12,14,22) & 68 \\
& (2,14,14,14,23,23,33) & 123 \\
& (3,11,18,21,26,27,35) & 141 \\
& (3,18,21,27,30,36,36) & 171 \\
& (4,12,14,14,14,28,30) & 116 \\
& (5,7,15,23,23,31,31) & 135 \\
& (5,9,16,20,26,30,33) & 139 \\
& (5,10,11,19,23,24,33) & 125 \\
& (6,7,18,21,25,31,33) & 141 \\
& (6,12,21,32,32,33,35) & 171 \\
& (6,16,16,18,24,34,34) & 148 \\
& (7,7,9,9,12,22,27) & 93 \\
& (7,8,8,8,9,10,25) & 75 \\
& (7,9,9,9,17,23,29) & 103 \\
& (8,11,24,25,32,34,37) & 171 \\
& (9,9,16,17,19,20,35) & 125 \\
& (9,10,22,24,26,32,38) & 161 \\
& (9,12,24,24,30,33,39) & 171 \\
& (10,19,30,33,33,37,43) & 205 \\
& (10,21,21,22,24,31,42) & 171 \\
& (10,21,33,36,39,40,40) & 219 \\
& (13,16,17,26,27,33,41) & 173 \\
& (13,16,19,22,27,37,39) & 173 \\
& (13,17,20,22,24,34,41) & 171 \\
& (13,21,31,35,38,39,44) & 221 \\
& (15,20,24,25,26,32,45) & 187 \\
& (17,17,25,30,33,39,44) & 205 \\
& (17,18,22,31,33,38,44) & 203 \\
& (18,19,24,24,26,38,44) & 193 \\
& (18,26,37,40,41,42,47) & 251 \\
& (19,20,29,31,36,39,47) & 221 \\
& (21,21,25,28,41,41,44) & 221 \\
& (21,28,36,39,39,39,51) & 253 \\
& (22,27,32,36,40,47,47) & 251 \\
& (22,30,30,44,44,44,46) & 260 \\
& (25,25,29,30,35,44,49) & 237 \\
& (25,33,35,40,41,42,53) & 269 \\
& (27,36,37,39,46,46,52) & 283 \\
& \color{#CC3300}{(49,49,49,49,49,49,49)} & \color{#CC3300}{343} \\
\hline
\hline \color{#003388}{(\alpha,\beta)=(5,4), \; k=1}
& \color{#CC3300}{1} & \color{#CC3300}{1} \\
\hline \color{#003388}{(\alpha,\beta)=(5,4), \; k=2}
& \color{#CC3300}{(8,8)} & \color{#CC3300}{8} \\
\hline \color{#003388}{(\alpha,\beta)=(5,4), \; k=3}
& \color{#CC3300}{(27,27,27)} & \color{#CC3300}{27} \\
\hline \color{#003388}{(\alpha,\beta)=(5,4), \; k=4}
& (22,22,33,44) & 121 \\
& (50,50,60,65) & 225 \\
& \color{#CC3300}{(64,64,64,64)} & \color{#CC3300}{256} \\
\hline \color{#003388}{(\alpha,\beta)=(5,4), \; k=5}
& (36,36,36,36,72) & 216 \\
& \color{#CC3300}{(125,125,125,125,125)} & \color{#CC3300}{625} \\
\hline \color{#003388}{(\alpha,\beta)=(5,4), \; k=6}
& (1,3,14,21,22,39) & 100 \\
& (3,57,81,96,99,114) & 450 \\
& (4,45,57,90,91,98) & 385 \\
& (5,5,40,45,57,68) & 220 \\
& (7,60,80,85,85,118) & 435 \\
& (10,25,41,55,55,84) & 270 \\
& (14,31,36,44,44,81) & 250 \\
& (16,56,64,64,88,112) & 400 \\
& (18,36,45,72,81,99) & 351 \\
& (21,38,45,75,92,99) & 370 \\
& (25,60,85,115,115,125) & 525 \\
& (30,35,52,77,88,108) & 390 \\
& (30,81,113,115,138,139) & 616 \\
& (34,68,80,110,112,136) & 540 \\
& (35,45,55,75,75,115) & 400 \\
& (36,40,68,82,112,113) & 451 \\
& \color{#CC3300}{(216,216,216,216,216,216)} & \color{#CC3300}{1296} \\
\hline
\end{array}


TITLE: Conditionally dependent and correlated but the expected conditional covariance is zero
QUESTION [1 upvotes]: Recall that
$$
\textrm{Cov}(X, Y | Z) = E(XY|Z) - E(X|Z)E(Y|Z)
$$
and note that quite trivially we have
$$
X \perp \!\!\! \perp  Y | Z \Longrightarrow \textrm{Cov}(X,Y|Z) = 0 \Longrightarrow E \textrm{Cov}(X,Y|Z)
$$
I have found examples where $X$ and $Y$ are not conditionally independent given $Z$ but the conditional covariance is zero ($Y = X + \varepsilon_Y$, $Z=X+Y+\varepsilon_Z$ where $X, \varepsilon_Y, \varepsilon_Z \sim \mathcal{N}(0,1)$ independently does the job).
Can anyone think of an example where $X$ and $Y$ are not conditionally independent given $Z$, the conditional covariance is non-zero but the expected conditional covariance is zero? Preferably $X$ and $Y$ should hav densities wrt. Lebesgue but any examples are welcome.
Is it even possible to find an example like this?
EDIT:
I think maybe I've found a solution where $X$ and $Y$ are independent uniforms on $[-1,1]$ and $Z = XY$. Then $E(XY | Z) = XY$ and I think $E(X|Z)=E(Y|Z)=0$ but I have a hard time showing the last bit. Any ideas?

REPLY [1 votes]: A simple example might be $Z$ and $X$ independently and uniformly distributed on $[-1,1]$, and $Y=XZ$.
Then $E(XY|Z)=E(X^2Z|Z)=Z/3$, $E(X|Z)=0$, $E(Y|Z)=E(XZ|Z)=0$, so $\text{Cov}(X,Y|Z)=Z/3$.
But the expected value of the covariance is $E(Z/3)=0$.


TITLE: What does it mean for this exact sequence to split?
QUESTION [1 upvotes]: On page 627 of Vector Fields on Spheres, Adams writes:

Our first concern is to show that the following exact sequence splits.
  $$\mathbb Z = \tilde K_{\mathbb R}(\mathbb R P^{4t}/\mathbb RP^{4t-1}) \xleftarrow{i} \tilde K_\mathbb R (\mathbb RP^n/\mathbb RP^{4t-1}) \xleftarrow{j} \tilde K_\mathbb R(\mathbb RP^n/\mathbb RP^{4t}).$$

I understand the definition of a split short exact sequence. However, I cannot find anything about a split sequence of length three. What does Adams mean by 'the following exact sequence splits'?
It appears that to prove this claim, Adams shows $j$ is a monomorphism and $i$ is an epimorphism. This implies that
$$0 \leftarrow \mathbb Z = \tilde K_{\mathbb R}(\mathbb R P^{4t}/\mathbb RP^{4t-1}) \xleftarrow{i} \tilde K_\mathbb R (\mathbb RP^n/\mathbb RP^{4t-1}) \xleftarrow{j} \tilde K_\mathbb R(\mathbb RP^n/\mathbb RP^{4t}) \leftarrow 0$$
is exact.

REPLY [0 votes]: A sequence $A \to B \to C$ is a split exact sequence if it can be extended to a short exact sequence $0 \to A \to B \to C \to 0$ that splits.
As stated in the question, Adams shows that we can extend to an exact sequence
$$0 \leftarrow \mathbb Z = \tilde K_{\mathbb R}(\mathbb R P^{4t}/\mathbb RP^{4t-1}) \xleftarrow{i} \tilde K_\mathbb R (\mathbb RP^n/\mathbb RP^{4t-1}) \xleftarrow{j} \tilde K_\mathbb R(\mathbb RP^n/\mathbb RP^{4t}) \leftarrow 0.$$
This sequence splits follows from the following easy lemma: any SES $0 \to A \xrightarrow{j} B \xrightarrow{i} \mathbb Z \to 0$ splits. Since $i$ is surjective, chose some $b \in B$ that maps to 1. Then define a section $s : \mathbb Z \to B$ by $s(1) = b$.


TITLE: Suppose that $f'$ exists and $\left\lvert f'(x)\right\rvert\le M$ on $[a,b]$.
QUESTION [2 upvotes]: Show that any Riemann sum $\sigma$ of $f$ over any partition $P$ of $[a,b]$ satisfies$$\left\lvert\sigma - \int_a^bf(x)dx\right\rvert\le M(b-a)\lVert P\rVert$$.
I am having trouble with this one and haven't been able to find the answer anywhere. I've tried applying the Mean Value Theorem for integrals to obtain:$$\begin{aligned}\left\lvert f'(c_j)\right\rvert=\frac{\left\lvert f(x_j)-f(x_{j-1})\right\rvert}{x_j-x_{j-1}}&\le M\:(\text{for some }c_j\in[x_{j-1},x_j])\\\implies\left\lvert f(x_j)-f(x_{j-1})\right\rvert&\le M(x_j-x_{j-1})\\\implies\sum_{j=1}^n\left\lvert f(x_j)-f(x_{j-1})\right\rvert&\le\sum_{j=1}^nM(x_j-x_{j-1})\\\implies\left\lvert f(b)-f(a)\right\rvert&\le M(b-a)\end{aligned}$$
but I don't know where to go from here or if I'm even on the right track. Would appreciate some help.
(This question is from page 151 of Trench: Introduction to Real Analysis).

REPLY [1 votes]: First suppose $P : a \leq b$ is the trivial partition.  Then $\sigma = f(c^*)(b-a)$ for some $c^* \in [a,b]$ and, by the integral mean value theorem, there is some $c \in [a,b]$ such that $\int_a^b f(x)\,dx = f(c)(b-a).$  Therefore,
$$\left|\sigma - \int_a^b f(x)\,dx\right| = \Big|f(c^*)(b-a) - f(c)(b-a)\Big| = \Big|f(c^*)-f(c)\Big| \cdot (b-a)$$
To estimate this last quantity, use the derivative mean value theorem to show there is some $d$ between $c^*$ and $c$ such that $$\Big|f(c^*)-f(c)\Big| = |f'(d)| \cdot |c^*-c| \leq M (b-a)$$
so that
$$\left|\sigma - \int_a^b f(x)\,dx\right| \leq M(b-a)^2$$

Now suppose $P : a = x_0 \leq x_1 \leq \ldots \leq x_n = b.$  Then if we write
$$\sigma = \sum_{k=1}^n\sigma_k \quad \text{ where } \quad \sigma_k = f(c_k)(x_k-x_{k-1})\\ \int_a^b f(x)\,dx = \sum_{k=1}^n \int_{x_{k-1}}^{x_k} f(x)\,dx$$
then by the triangle inequality and the previous work applied to each subinterval of the partition:
$$\left|\sigma - \int_a^b f(x)\,dx\right| = \left|\sum_{k=1}^n\left(\sigma_k - \int_{x_{k-1}}^{x_k} f(x)\,dx\right)\right| \leq \sum_{k=1}^n \left|\sigma_k - \int_{x_{k-1}}^{x_k} f(x)\,dx\right| \leq \sum_{k=1}^n M(x_k-x_{k-1})^2$$
We finish by noting that $x_k - x_{k-1} \leq \|P\|,$ so
$$\left|\sigma - \int_a^b f(x)\,dx\right| \leq M \sum_{k=1}^n (x_k-x_{k-1})(x_k-x_{k-1}) \leq M\sum_{k=1}^n(x_k-x_{k-1})\|P\| = M(b-a)\|P\|$$


TITLE: Sound Waves + Closed Box --> What happens under movement?
QUESTION [1 upvotes]: Setup:
We have a closed, and from the outside isolated, box with two sound-emitting-generators placed at opposing ends, and one microphone placed in the middle (--> picture).

The sensors are all placed in such a way that the microphone does not pick up any noise, as long as the box is in its initial state [total noise cancellation through sound-wave peak and valley annihilation].
Moreover, let's assume the medium of the box is simply air for now.
Question:
If we move the box, will the microphone pick up any noise/sound?
My Thoughts:

One the one hand, the relative position between the noise-emitting sensors and the microphone is not changing at any point throughout the movement. Thus, the wave-constellation does not change (?), and thus the microphone should pick up no noise.
On the other hand, the movement should move the bounding-walls closer towards an already before-the-movement-started-emitted wave which should let this wave then create a different echo-effect than without movement. This would most likely change the wave-constellation and destroy the perfect noise-cancelling, and thus, the microphone should pick up noise.

Please help me determine which thought of mine (or none) is correct :S

REPLY [4 votes]: By Galilean invariance a box moving at constant velocity and a box at rest are indistinguishable from inside the box. In that case, the microphone should not pick any "noise".
The analysis is more involved if and when the box accelerates. A simple way of accounting for acceleration is to consider a box at rest under the influence of a horizontal gravitational field. Say the box is accelerating rightwards and pseudo-gravity is then directed to the left. In that case, air will have higher density near the left edge and lower density near the right edge kind of like what happens in earth's atmosphere. It seems however that sound speed does not depend much on air's density and is much more sensitive to variations in temperature. In any case, if the acceleration is large enough and/or the box large enough and/or the microphone sensitive enough, then it should pick up some noise.


TITLE: Minimum distance from uniformly distributed points
QUESTION [3 upvotes]: Let $P=\{p_1,\dots,p_n\}$ be $n$ points on the unit square with each of their coordinates drawn from a uniform distribution on $[0,1]$.
Then we add an extra point $q$ by the same distribution and we define
$d_i=\|q-p_i\|$.
Would like to know what is the average and the minimum of the $d_i$'s. I assume that $d_i$'s are independent, so the are identically distributed. Am I right?
For the average distance we have $E[\text{Mean}(d_1,\dots,d_n)] = E[d_1]$ since they are all i.i.d. and the expectation can be found by the integral
$$\int_0^1\int_0^1\int_0^1\int_0^1\sqrt{(x_1-x_2)^2+(x_3-x_4)^2}dx_1dx_2dx_3dx_4$$
which does not have a nice closed form but its value is approximately $0.5214$.
However, I am not sure how to figure out how $Z=E[\text{Min}(d_1,\dots,d_n)]$ depends on $n$.
I would expect that asymptotically it behaves like $c/n$. I say this because the probability that $Z<r$ can be bounded from above (unless I am wrong) by the area of $n$ disks with radius $r$.
When I generated numbers to test this, it seems that the asymptotic behaviour is closer to $1/n^{1/2}$ than $c/n$. Is there any straightforward way to get this exponent?

REPLY [0 votes]: See D. Moltchanov Distance distributions in random networks (Ad Hoc Networks 10(6), 2012).
They give the distribution to the $n^{\text{th}}$ nearest neighbour of $q$ as a Gamma distribution.


TITLE: Infinite Series Convergence - Counter Example
QUESTION [2 upvotes]: I'm trying to prove that if $\sum_{n=1}^\infty a_n$ and $\sum_{n=1}^\infty b_n$ are convergent series and $c_n = \max\{a_n, b_n\}$ then  $\sum_{n=1}^\infty c_n$ doesn't necessarily converge.
I believe I've come up with a counter-example but to be honest I'm not too confident in my ability to work with series so I was wondering if I could get some feedback.
Let $\sum_{n=1}^\infty a_n = \sum_{n=1}^\infty \frac{(-1)^n}{n}$ and $\sum_{n=1}^\infty b_n = \sum_{n=1}^\infty \frac{1}{n^2}$.
These series both converge but $c_n = \frac{1}{n}$ if $n$ is even and $c_n = \frac{1}{n^2}$ if $n$ is odd, so I don't think $\sum_{n=1}^\infty c_n$ converges.
The reason I think this is because $\sum_{n=1}^\infty c_{2n} = \sum_{n=1}^\infty \frac{1}{2n} = \frac{1}{2}\sum_{n=1}^\infty \frac{1}{n}$ which diverges since it's a multiple of the harmonic series. Since the $c_n$ terms with odd indices are all positive, the sum of the two should be divergent as well.
Could anyone confirm I'm thinking about this correctly or point out a flaw in my reasoning if I'm not?
Thank you

REPLY [3 votes]: Your proof looks good. Even simpler counterexample is $a_n=\frac{(-1)^n}{n}$ and $b_n=-a_n$.


TITLE: Uniform Boundedness Principle question about the proof.
QUESTION [0 upvotes]: I have a short question about the proof found here:
http://mathonline.wikidot.com/the-uniform-boundedness-principle
It shows that given an $x$ s.t its norm is $1$., then the linear functionals is bounded. However, I do not see how it implies for any $x$, $\|T(x)\|\leq M \|x\|$ Whats the trick to extend the boundedness to all x?

REPLY [1 votes]: $$\|T(x)\| = \|T(\frac{x}{\|x\|})\|x\|\| = \|T(\frac{x}{\|x\|})\| \cdot \|x\| \leq M\|x\|$$
for any $x$, where we used the linearity of $T$ and the homogeneity of the norm.


TITLE: Probability : find $P(|X-y|<1/2)$ for a uniform distribution of $x,y$
QUESTION [2 upvotes]: The question :
Two guys pick a random point between $[0,2]$ (uniform distribution)      . find the probability that the distance between the points is < $0.5$
$$X - \text{first point} $$
$$Y - \text{second point}$$
so because they are random $$f(x,y)=f(x)*f(y)=0.25$$
So I wrote $$P(|X-Y|<0.5) = P(-0.5<x-y<0.5)= P(x-y<0.5)-p(x-y<-0.5)
=P(x<y+0.5)-p(x<y-0.5)$$
using the integrals
$$\int_0^2 \int_0^{y+0.5} 0.25 dxdy-\int_0^2 \int_0^{y-0.5}0.25 dxdy $$
I get $0.5$ and the answer is $7/16$ according to my professor.
What am I'm doing wrong ? I can draw the graph and see the limits but I think it's faster like that.
Thanks

REPLY [1 votes]: Well your domain of integration is wrong. For example, $y+0.5$ goes beyond $2$.

It is always advisable to sketch a diagram.
A quick way to solve this question is simply calculate the corresponding area multiplied by the density.
$$\frac14 \left( 4 - 2 \times \frac12 \left( \frac32 \right)^2 \right) =1-\frac{9}{16}=\frac7{16}$$
Edit:
\begin{align}
&\int_0^2 \int_0^{y+0.5} f(x,y) \,dx \, dy - \int_0^2 \int_0^{y-0.5}f(x,y) \,dx \, dy \\
&=\int_0^2 \int_0^{y+0.5} \frac14 \mathbb{1}_{0 \leq x \leq 2, 0 \leq y \leq 2 } \,dx \, dy - \int_0^2 \int_0^{y-0.5}\frac14 \mathbb{1}_{0 \leq x \leq 2, 0 \leq y \leq 2 }  \,dx \, dy \\
\\&=\int_0^2 \int_0^{\min(2,y+0.5)}  \frac14\,dx \, dy-\int_{\frac12}^2 \int_0^{y-0.5} \frac14 \,dx\,dy
\end{align}


TITLE: Why are spherical representations subquotients of unramified principal series?
QUESTION [6 upvotes]: I'm trying to learn the basics of the representation theory of $p$-adic groups and I'm stuck on a few things:
Let $G$ is a connected split reductive group over a non-archimedean local field $F$, and $K=G(\mathcal{O})$, a hyperspecial maximal compact subgroup of $G(F)$. Then there are two facts that apparently go hand in hand:

The Iwahori-Hecke algebra $H(G//K)$ is commutative.
If $\pi$ is any irreducible admissible (complex) representation of $G(F)$, then dim$(\pi^K) \leq 1$.

For the first statement there is a trick: one uses the Cartan decomposition to show that there is an anti-automorphism on the Hecke algebra that is the identity. But I don't see how to prove the second fact -- does it follow quickly from the first fact?
There is also this statement: For any irreducible admissible $\pi$, $\pi^K \neq 0$ if and only if $\pi$ is a Jordan-Holder component of an unramified principal series representation of $T(F)$, where $T$ is a maximal split torus in $G$.
I would appreciate any help on how these statements are proven. Part of the reason I'm confused is that the source I'm looking at seems to me to suggest that these statements follow from the first statement, but after looking on the internet, it seems that the statement about unramified principal series is a deep result of Satake, reproven by Casselman.

REPLY [9 votes]: Statement 2. comes from the following classical fact whose proof can be found in e.g.  Bushnell and Kutzko, "The admissible dual of ${\rm GL}(N)$ via compact open subgroups". This is a particular case of Proposition (4.2.3), page 147 of loc. cit. I state it in your case:
The following sets are in natural bijection:
(i) equivalence classes of irreducible representations $\pi$ such that $\pi^K \not= 0$;
(ii) Isomorphism classes of simple ${\mathcal H}(G//K)$-modules.
Of course, in your case, since ${\mathcal H }(G//K)$ is commutative, its simple left modules are $1$-dimensional.
For your last statement. There are several good references for the unramified principal series. Among them:
Casselman's lecture notes : Introduction to the theory of admissible representations of $p$-adic reductive groups (available on his web page).
Casselman, W. The unramified principal series of -adic groups. I. The spherical function. Compositio Math. 40 (1980), no. 3, 387–406.
Important remark. Your last statement, as it is stated is false, or,  to be true, it depends on what you mean by "unramified principal series". If you take as a definition that an unramified principal series is with no restriction a representation parabolically induced from an unramified character of a maximal split torus,  then for your statement to be true you have to replace $K$ by an Iwahori subgroup of $G$. In that case the corresponding theorem is due to A. Borel (Invent. Math. 35, 1976, 233--259). For the case of your maximal compact subgroup $K$, only the direct implication holds. A classical counter-example is the steinberg representation. It is an irreducible (sub)quotient of some unramified principal series, but it is not $K$-spherical (but of course it is Iwahori-spherical).


TITLE: How to prove the bisector vector of the angle formed by three consecutive points on a helix is perpendicular to direction
QUESTION [0 upvotes]: I have a problem shown in the title.
The problem comes from a paper named "DEFINING THE AXIS OF A HELIX"1, where it stated that "Construct vector PI from the origin to carbon alpha 2 (CA2). From CA2, construct vectors A and B to CA1, and CA3, respectively. The bisector of the angle defined by A and B will be perpendicular to the helix axis and will intersect it." I am wondering how to prove this? Does length of vector A and B should be the same?
Thank you.

1Peter C. Kahn, Defining the axis of a helix, Computers & Chemistry, Volume 13, Issue 3, 1989, Pages 185-189

REPLY [1 votes]: In the following I'm assuming some regularity of your helix and the placement of the points you consider on it.
Let's parametrize the helix as follows.
$$
h(t) = (a\cos t, a\sin t, bt)\quad for \quad t \in \mathbb R
$$
with real constants $a,b > 0$. The first coordinate of $h(t)$ is the $x$-coordinate, the second is the $y$-coordinate, and the third is the $z$-coordinate with coordinate axis as in your picture. The axis of symmetry is the $z$-axis. As $t$ increases, $h(t)$ spirals upwards around the $z$-axis with "radius" $a$. $b$ is the "height covered by the helix in one complete revolution".
By symmetry, we can assume
$$
P1 = h(0) = (a,0,0).
$$
We want $P1$ to be "in the middle" between the points $P1+A$ and $P1+B$. This means we pick $P1+B$ at height (i.e. $z$-coordinate) $b\tau$ for some $\tau > 0$ and $P1+A$ at the negative height $-b\tau.$ Note that a point on the helix is uniquely determined by its height, since given the height (i.e. $z$-coordinate), we can reconstruct the parameter $t$ and thus the whole point $h(t)$. Thus, we must have
$$
P1+B = h(\tau) \quad and \quad P1+A = h(-\tau).
$$
This leads us to
$$
\begin{align}
B & = h(\tau)-P1 \\
& = h(\tau)-h(0) \\
& =(a\cos\tau-a,a\sin\tau,b\tau),
\end{align}
$$
and
$$
\begin{align}
A & = h(-\tau)-P1 \\
& = h(-\tau)-h(0) \\
& =(a\cos(-\tau)-a,a\sin(-\tau),-b\tau) \\
& =(a\cos\tau-a,-a\sin\tau,-b\tau).
\end{align}
$$
From this, we get
$$
\frac{1}{2}(B+A) = (a\cos\tau-a,0,0).
$$
Now, the line $L$ through $P1$ bisecting the segment from $P1+A$ to $P1+B$ consists of the points
$$
\begin{align}
P1+\lambda\frac{1}{2}\left((P1+B)+(P1+A)\right) & = P1+\lambda\frac{1}{2}(B+A) \\
& = (a,0,0)+\lambda(a\cos\tau-a,0,0) \\
& = (a+\lambda (a\cos\tau-a),0,0)
\end{align}
$$
with parameter $\lambda\in\mathbb R.$ We want this line to intersect the helix axis, i.e. the $z$-axis. To this end we have to solve
$$
0 = a+\lambda (a\cos\tau-a)
$$
and arrive at
$$
\lambda = \frac{1}{1-\cos\tau}.
$$
Here we must exclude the case $\cos\tau = 1.$ But this is perfectly reasonable, since $\cos\tau=1$ iff $\tau \in 2\pi\mathbb Z$ iff $A$ and $B$ are parallel to the $z$-axis iff $P1+B$ and $P1+A$ are located (in the direction of the $z$-axis) "over" resp "under" $P1$ on the helix. In this case, the midpoint of the segment from $P1+A$ to $P1+B$ is the point $P1$. So in this case the line $L$ degenerates to the point $P1$. It's reasonable to exclude this case.
So we have that the line $L$ from above intersects the $z$-axis. Since the direction of $L$ is given by $\frac{1}{2}(B+A)$, we see from the coordinates of this vector calculated above that $L$ is perpendicular to the $z$-axis. And to answer the final part of your question, yes, in all these calculations $A$ and $B$ have the same length. Otherwise we don't have enough symmetry.


TITLE: Showing $\int_0^\infty\frac {r} {x^2}e^{-x^2-\frac {r^2} {x^2}}dx=\int_0^\infty e^{-x^2-\frac {r^2} {x^2}}dx$
QUESTION [1 upvotes]: As part of a parameter integral problem, I need to show that given the function $$
\operatorname{F}\left(r\right) =
\int_{0}^{\infty}\exp\left(-x^{2} - \frac{r^{2}}{x^{2}}\right){\rm d}x\,,\qquad \operatorname{F}\hspace{0.1mm}'\!\left(r\right) =
-2\operatorname{F}\left(r\right)\,,
$$
which amounts to what the title demands. However I cannot find a way to do so, either by integration by parts, substitution or anything else, even though it should be simple.
What am I missing $?$.

REPLY [3 votes]: Use a substitution $x\mapsto r/x$. It may be easier to follow if you write $y=r/x$ so the right-hand side transforms to $\int_0^\infty e^{-r^2/y^2-y^2}dy$.


TITLE: Can I apply the formula to the integration?
QUESTION [1 upvotes]: Is it possible to use this formula$\int_{}^{}e^{x}cosx = \frac{1}{2}e^{x}(sinx + cosx)$ for $\int_{a}^{b}e^{-2.4x}cos(2x + 0.8)dx$?
Or should we calculate step by step?

REPLY [1 votes]: Let's pose $t = 2x + 0.8$. Then, $x = \frac{t - 0.8}{2}$
and $dx = \frac{1}{2}dt$.
By substituting, you get:
$$\int \frac{1}{2}e^{-2.4\frac{t-0.8}{2}}\cos(t)dt  = \frac{1}{2}e^{0.96}\int e^{-1.2t}\cos(t)dt.$$
Now, you can use the formula you know that Dr. Sonnhard Graubner proposed in its post. Finally, substitute back the $x$.


TITLE: Taylor expansion of charge density in Jackson's book
QUESTION [1 upvotes]: I am learning from Jackson (3r edition), where I found one concept very confusing, that is Taylor expansion of charge density. (This is given in section "1.7 Poisson and Laplace equations" p.n:35)
I will write some equations first.
$$ {\Phi}_a(x) = \frac{1}{4{\pi}{\epsilon_0}}\int \frac{{\rho}(x')}{\sqrt{(x - x')^2 + a^2}}d^3x'  $$
Now we want to find out potential such that a tends to zero.
$$ \nabla^2{\Phi}_a(x) = \frac{1}{4{\pi}{\epsilon_0}}\int{\rho}(x') \nabla^2\frac{1}{(r^2 + a^2)^\frac{1}{2}}d^3x'  $$
$$ \nabla^2{\Phi}_a(x) = -\frac{1}{4{\pi}{\epsilon_0}}\int{\rho}(x') \frac{3a^2}{(r^2 + a^2)^\frac{5}{2}}d^3x'  $$
I understood this until above step, but now I didn't got the next step
$$ \nabla^2{\Phi}_a(x) = -\frac{1}{{\epsilon_0}}\int_0^R  \frac{3a^2}{(r^2 + a^2)^\frac{5}{2}} \left[{\rho}(x) + \frac{r^2}{6}\nabla^2{\rho} + ....... \right]r^2 dr + O(a^2) $$
Jackson says that we gonna expand ${\rho}(x')$ around x' = x., but the expansion of ${\rho}(x')$ should also contain the first order derivative of ${\rho}(x')$ like $\nabla{\rho}$,  also the taylor expansion of the second term should contain 2 at the denominator but it's 6, and how the last term of $O(a^2)$
So what I am thinking is that Taylor expansion should be $\left[{\rho}(x) + r\nabla{\rho} + \frac{r^2}{2}\nabla^2{\rho}\right]$
I know I am wrong but I don't know what is the answer. Any help is appreciated.

REPLY [1 votes]: Firstly, your form of Taylor expansion is wrong. The right form is here: https://en.wikipedia.org/wiki/Taylor_series#Taylor_series_in_several_variables .
It seems like a special condition with a parameter $R$, and the integrals of some Taylor terms are zero. As it is not mentioned in the book, these zero integrals should be analyzed by symmetry.


TITLE: Largest elementary neighbourhood
QUESTION [0 upvotes]: The real projective space $\mathbb{R}P^n$ can be defined as the quotient space of $\mathbb{S}^n$by the equivalence relation that identifies antipodal points. The largest open set of $\mathbb{S}^n$ that contains exactly one representative of each equivalence class is easily seen to be an open hemisphere.
Consider now the complex projective $\mathbb{C}P^n$ as the quotient space of $\mathbb{S}^{2n+1} \subset \mathbb{C}^{n+1}$ by the $\mathbb{S}^1$ action given by
$\lambda \cdot (z_1, \dots, z_{n+1}) = (\lambda z_1, \dots, \lambda z_{n+1}), \qquad \lambda \in \mathbb{S}^1, \, (z_1, \dots, z_{n+1}) \in \mathbb{S}^{2n+1}.$
In analogy with the real case, what is now the largest hypersurface of $\mathbb{S}^{2n+1}$ that contains exactly one representative of each equivalence class?

REPLY [2 votes]: The question is not really well posed as it stands. First, the open hemisphere doesn't contain "exactly one representative of each equivalence class," because it doesn't contain any representatives of the equivalence classes of points on the equator. The best we can say is that it contains at most one representative of each equivalence class.
Second, the hemisphere isn't "the largest" such open set; it's merely a maximal one, meaning that it's not properly contained in any larger open set that contains at most representative of each class. There are plenty of other maximal open sets that are not hemispheres, such as one whose boundary is a deformation of the equator, as pictured in the drawing below.
That said, it does make sense to ask for a maximal hypersurface in $\mathbb S^{2n+1}$ that contains at most one representative of each class. One such hypersurface is the set $W$ consisting of all $z = (z^1,\dots,z^{n+1})\in \mathbb S^{2n+1}$ such that $z^{n+1}$ is real and positive. Its image in $\mathbb C\mathbb P^n$ is the affine subspace consisting of all points $[z^1:\dots:z^{n+1}]$ such that $z^{n+1}\ne 0$.
To see that it's maximal, the basic idea is to check that any hypersurface $\widetilde W$ that strictly contains $W$ must contain at least one point where $\operatorname{Re} z^{n+1}=0$, and a neighborhood of that point in $\widetilde W$ will also contain points where $\operatorname{Re} z^{n+1}<0$; but the equivalence class of any such point is already represented by a point in $W$.


TITLE: Generalization of nilpotent matrix property: I-A has an inverted matrix
QUESTION [1 upvotes]: It can be proven that if $A$ is a nilpotent square matrix then $I-A$ can be inverted and the inverted matrix takes the form $I+A+A^2+A^3...+A^{(k-1)}$
where $k$ is the $k$ in $A^k=0$
I am to find the generalization of the property.
Prove that if square matrix A is nilpotent, then $aI-bA$ can be inverted, where $a \ne o$ and $a$ and $b$ are real numbers.
We are still in the beginning of the course, so no eigenvalues or upper triangles. I tried to prove it in the same fashion as the basic property was proven, but couldn't figure it out. Later realized that it doesn't seem to have the same kind of formula as above and that I don't even need to find the formula for the inverted matrix. I just need to prove that for $aI-bA$ an inverted matrix can be found.

REPLY [0 votes]: I will assume that both $a$ and $b$ are non-zero. In this case, we can write
$$
aI-bA = a(I - \frac ba A)
$$
Note that $\frac ba A$ is a nilpotent matrix of the same order as $A$ (that is, $[\frac ba A]^k= 0$ if and only if $A^k=0$). So, we have a formula for $(I - \frac ba A)^{-1}$.
From there, note that
$$
[a(I - \frac ba A)]^{-1}= a^{-1} (I - \frac ba A)^{-1}
$$

REPLY [0 votes]: You only have to prove that $\ker bA-aI=\{0\}$. Let $v\in \ker bA-aI$, that is to say $bAv=av$.
It's easy to prove by induction that $\forall m, b^mA^mv=a^mv$.
With $m=k$ you get $0=a^kv$. Since $a\neq 0, v=0$.


text:
\newpage

\appendix
\begin{comment}

\section{Computing description length}
We generally follow the description of~\citep{Blier2018}.
The problem of calculating $L_{\mathcal{M}}(D)$, $D = \{x_i, y_i\}_{i=1}^k$ is considered as a problem of transferring outputs $y_i$ one-by-one, in a compressed form, between two parties, Alice (sender) and Bob (receiver). Alice has the entire dataset $\{x_i, y_i\}$, while Bob only has inputs $\{x_i\}$.
Before the transmission starts, both parties agreed on the initialization of the model $\mathcal{M}$, order of the inputs $\{x\}$, random seeds, and the details of the learning procedure. Outputs $\{y_i\}$ are sequences of tokens from a vocabulary $|V|$.

The very first output $y_1$ can be send by using not more than $c = |y_1| \cdot \log |V|$ nats, using a na\"ive encoding. After that, both Alice and Bob update their learners using the example $(x_1, y_1)$, available to both of them, and get identical instances of $\mathcal{M}_1$.

Further transfer is done iteratively under the invariant that both Alice and Bob start every step $t$ with exactly the same learners $\mathcal{M}_{t-1}$ and finish with identical $\mathcal{M}_t$. At step $t$ Alice would use $\mathcal{M}_{t-1}$ to encode the next output $y_t$. This can be done using $\left(-\log p_{\mathcal{M}_{t-1}}(y_{t} | x_{t})\right)$ nats~\citep{Mackay2003}. Since Bob has exactly the same model, he can decode the message to obtain $y_{t}$ and use the new pair $(x_{t}, y_{t})$ to update his model and get $M_{t}$. Alice also updates her model, and proceeds to sending the next $y_{t+1}$ (if any), encoding it with the help of $\mathcal{M}_{t}$.

Overall, this procedure gives us Eq.~1 from Section~2 of the main text:
$$

    L_{\mathcal{M}}(D) = - \sum_{t=2}^k \log p_{\mathcal{M}_{t-1}}(y_t | x_t) + c.
$$

\end{comment}

\section{Can seq2seq learners multiply by 3?}
In our experiments on the \textit{Multiply-or-Add} task we saw that LSTM-s2s learners are able to learn to multiply by 2 from a single example.

A natural further question is whether these learners can learn to multiply by larger numbers?

Here we only provide a preliminary study in a hope to inspire more focused studies.

We build a task that is similar to \textit{Multiply-or-Add}, but centered around multiplication by 3 instead of 2. The single training example represents a mapping of an input string $a^l$ to an output string $b^{3l}$. As test inputs, we use $a^m$ with $m$ coming from an interval $[l - 3, l + 3]$.

Since $3x$ can be represented as a combination of addition and multiplication in several ways ($3x = x + 2x = 2x + x$),
we consider $4$ different candidate rules. As before, by \texttt{mem} we denote the constant mapping from $a^m \rightarrow b^{3l}$. \texttt{mul1} represents the mapping $a^m \rightarrow b^{2l + m}$. \texttt{mul2} corresponds to $a^m \rightarrow b^{l + 2m}$ and \texttt{mul3} denotes $a^m \rightarrow b^{3m}$. The ``explanation'' \texttt{mul1} is akin to the \texttt{add} rule in the \textit{Multiply-or-Add} task.
We use the same hyperparameters and training procedure described in Section~4.

We report the results in Table~\ref{tab:mult3}.
Like the results observed in the \textit{Multiply-or-Add} task, both CNN-s2s and Transformer learners show a strong preference for the \texttt{mem} rule while LSTM-based learners switch their generalization according to the length of the training example $l$. Indeed, for CNN-s2s and Transformer, we note an FPA-\texttt{mem}>0.97 independently of $l$ (with $L$-\texttt{mem} significantly lower than others). LSTM-s2s att.\ learners start inferring the \texttt{mem} rule for $l=5$ (FPA=0.64, $L$=2.44), then switch to comparable preference for \texttt{mul2} and \texttt{mul3} when $l=10$, and finally show a significant bias toward the \texttt{mul3} hypothesis for $l \in \{15,20\}$ (e.g. FPA-\texttt{mul3}=0.76 for $l=15$). LSTM-s2s no att.\ learners are also subject to a similar switch of preference. That is, for $l=5$, these learners have a significant bias toward \texttt{mul1} (FPA=0.49). Strikingly, when $l=10$,  $92\%$ LSTM-s2s no att.\ learners inferred perfectly the \texttt{mul2} rule after one training example. Finally, we observe again another switch to approximate \texttt{mul3} for $l \in \{15,20\}$.

Overall, while CNN-s2s and Transformer learners show a significant and robust bias toward \texttt{mem}, LSTM-based learners generalize differently depending on the training input length. In particular, our results suggest that these learners avoid adding very large integers by switching to the multiplicative explanation in those cases. Answering our initial question, we see that LSTM-based learners \textit{can} learn to multiply by 3 from a single example.

\begin{savenotes}
\begin{table}
\centering
\resizebox{1\textwidth}{!}{
    \begin{tabular}{lccccccccccc}
    \toprule
    & & \multicolumn{4}{c}{FPA} &
    \multicolumn{4}{c}{$L$, nats}\\
    & length $l$ & \texttt{mul1} & \texttt{mul2} & \texttt{mul3} & \texttt{mem} &
    \texttt{mul1} & \texttt{mul2} & \texttt{mul3} & \texttt{mem} \\
    \midrule
    LSTM-s2s no att.
     & 20 & 0.00 & 0.01&
    0.78 & 0.00 & 52.27 & 22.20 & \textbf{1.17}$^*$ & 77.75 \\
    & 15 & 0.00 & 0.13&
    0.45 & 0.00 & 40.46 & 13.22 & \textbf{6.14}$^*$ & 66.10   \\
    & 10 & 0.00 & 0.92 &
    0.00 & 0.00 & 26.48 &\textbf{0.65}$^*$ & 22.26 &  53.81\\
    & 5 & 0.49 & 0.00 &
    0.00 & 0.00 & \textbf{1.97}$^*$ &  26.50 &  54.97 & 36.13\\
    \midrule
    LSTM-s2s att.
     & 20\footnote{Only 21\% of learners succeeded in learning the training example in this setting.} & 0.00 & 0.19&
    0.62 & 0.00 & 36.76 & 20.35 & \textbf{9.35}$^*$ & 49.34\\
    & 15\footnote{Only 51\% of learners succeeded in learning the training example in this setting.} & 0.00 & 0.14&
    0.76 & 0.00 & 37.84 &  18.42 & \textbf{5.53}$^*$ & 56.43\\
    & 10 & 0.02 & 0.45 &
    0.49 & 0.00 & 29.83 & 11.67 & \textbf{8.96} & 45.47 \\
    & 5 & 0.01 & 0.03 &
    0.00 & 0.64 & 32.97 & 48.26 & 60.38 & \textbf{2.44}$^*$  \\
    \midrule
    CNN-s2s
     & 20 & 0.00 & 0.00&
    0.00 & 0.99 & 263.82 & 262.01 & 261.71 & \textbf{0.02}$^*$ \\
    & 15 & 0.00 & 0.00&
    0.00 & 1.00 & 250.97 & 253.32 & 253.08 & \textbf{0.00}$^*$ \\
    & 10 & 0.00 & 0.00&
    0.00 & 1.00 & 243.17 & 245.16 & 248.28 & \textbf{0.00}$^*$ \\
    & 5 & 0.00 & 0.00&
    0.00 & 1.00 & 258.10 & 257.79 & 264.06 & \textbf{0.00}$^*$ \\
    \midrule
    Transformer
     & 20 & 0.00 & 0.00&
    0.00 & 0.97 & 37.90 & 51.47 & 57.57 & \textbf{5.31}$^*$ \\
    & 15 & 0.00 & 0.00&
    0.00 & 1.00 & 40.36 & 51.62 & 57.42 & \textbf{2.50}$^*$ \\
    & 10 & 0.00 & 0.00&
    0.00 & 1.00 & 38.05 & 49.88 & 55.61 & \textbf{2.47}$^*$ \\
    & 5 & 0.00 & 0.00&
    0.00 & 1.00 & 37.96 & 51.83 & 60.19 & \textbf{0.74}$^*$ \\
    \bottomrule
    \end{tabular}
  }
\caption{Multiplication by 3. FPA measures the fraction of seeds that generalize according to a particular rule. Description length $L$ is averaged across examples and seeds. The lowest $L$ are in bold and $*$ denotes stat.\ sig.\ difference in  $L$ ($p < 10^{-3}$, paired t-test).\label{tab:mult3}}
\end{table}
\end{savenotes}

\section{Robustness to changes in architecture}
\label{sec:hyperparam_archi}
In this section, we examine how changing different hyper-parameters affects learners' preferences for memorization, arithmetic, hierarchical and compositional reasoning. In particular, we vary the number of layers, hidden and embedding sizes of the different learners and test their generalization on \textit{Count-or-Memorization}, \textit{Add-or-Multiply}, \textit{Hierarchical-or-Linear}, and \textit{Composition-or-Memorization} tasks.

In all the experiments, we fix $l=40$ and $l=20$ for \textit{Count-or-Memorization} and \textit{Add-or-Multiply} respectively, $d=4$ for \textit{Hierarchical-or-Linear} and $M=36$ for \textit{Composition-or-Memorization}. Finally, we keep the same training and evaluation procedure as detailed in Section 4.2 of the main text. However, we use 20 different random seeds  instead of 100.

\subsection{Number of hidden layers ($N_{Layer}$)}
We experiment with the standard seq2seq learners described in the main paper and vary the number of layers $N_{Layer} \in \{1,3,10\}$. Results are reported in Table \ref{tab:nbrL}.

First, when looking  at the interplay between \texttt{mem} and \texttt{count} (Table \ref{tab:count-or-memnbrL}), we observe that, independently of $N_{Layer}$, more than $97\%$ of CNN-s2s and Transformer learners inferred \emph{perfectly} the \texttt{mem} rule (i.e.\ output $b^{40}$ for any given input $a^m$). Further, if the  preference for \texttt{count} decreases with the increase of $N_{Layer}$, LSTM-s2s att.\ learners display in all cases a significant bias toward \texttt{count} with a large FPA and an $L$ significantly lower than $L$-\texttt{mem} . However, we note a decline of the bias toward \texttt{count} when considering LSTM-s2s no att.\ learners. For $N_{Layer}=1$, $100\%$ of the seeds generalize to perfect \texttt{count}, versus $6\%$ for $N_{Layer}=10$. Note that this lower preference for \texttt{count} is followed by an increase of preference for \texttt{mem}. However, there is no significant switch of preferences according to $L$.

Second, we consider the \textit{Add-or-Multiply} task where we examine the three generalization hypothesis \texttt{add}, \texttt{mul}  and \texttt{mem}. Results are reported in Table \ref{tab:add-or-mulnbrL}. Similarly to the previous task, Transformer and CNN-s2s learners are robust to the number of layers change. They perfectly follow the \texttt{mem} rule with  FPA-\texttt{mem}=1.00. However, LSTM-based learners show a more complex behavior: If single-layer LSTM-s2s att.\ and no att.\ demonstrate a considerable bias for \texttt{mul} (FPA-\texttt{mul}>0.94), this bias fades in favor of \texttt{add} and \texttt{memo} for larger architectures.

Third, in Table \ref{tab:hierar-or-linearnbrL}, we observe that larger learners are slightly less biased toward \texttt{hierar} and \texttt{linear}. However, we do not observe any switch of preferences. That is, across different $N_{layers}$, CNN-s2s learners prefer the \texttt{linear} rule, whereas Transformers and, to a lesser degree, LSTM-based learners show a significant preference for the \texttt{hierar} rule.

Finally, we do not observe an impact of $N_{Layer}$ on the \textit{Composition-or-Memorization} task (see Table \ref{tab:comp-or-memnbrL}), demonstrating the robustness of biases w.r.t.~learners' size.

In sum, we note little impact of $N_{Layer}$ on learners' generalizations. Indeed, \textit{LSTM-based learners can learn to perform counting from a single training example, even when experimenting with  10-layer architectures.} For most tested $N_{Layer}$, they favor \texttt{mul} and \texttt{add} over \texttt{mem}. In contrast, Transformer and CNN-s2s perform systematic memorization of the single training example. Furthermore, independently of  $N_{Layer}$, Transformer and LSTM-based learners show a bias toward the \texttt{hierar} hypothesis over the \texttt{linear} one, while CNN-based learners do the opposite. Finally, the compositional experiments further support how inductive biases are barely influenced by the change of the number of layers.

\begin{table}
\centering
\captionsetup[subtable]{position = below}
    \begin{subtable}{1\linewidth}
        \centering
        \resizebox{0.5\textwidth}{!}{
        \begin{tabular}{lcccccccc}
        \toprule
        & & \multicolumn{2}{c}{FPA} &
        \multicolumn{2}{c}{$L$, nats}  \\
         & $N_{Layer}$  & \texttt{count} & \texttt{mem} &
         \texttt{count} & \texttt{mem}\\
        \midrule
        LSTM-s2s no att.
        & 1 & 1.00 & 0.00 &
        \textbf{0.01}$^*$ & 97.51 \\
        & 3 & 0.80 & 0.00 &
        \textbf{0.00}$^*$ & 60.80 \\
        & 10 & 0.06 & 0.47 &
        \textbf{16.89} & 22.02 \\
        \midrule
        LSTM-s2s att.
        & 1 & 0.99 & 0.00 &
        \textbf{7.84}$^*$ & 121.48 \\
        & 3 & 0.50 & 0.00 &
        \textbf{11.30}$^*$ & 57.57 \\
        & 10 & 0.39 & 0.22 &
        \textbf{22.86}$^*$ & 45.13 \\
        \midrule
        CNN-s2s
        & 1 & 0.00 & 0.98 &
        660.73 & \textbf{0.02}$^*$ \\
        & 3 & 0.00 & 1.00 &
        1685.18 & \textbf{0.00}$^*$ \\
        & 10 & - & - &
        - & - \\
        \midrule
        Transformer
        & 1 & 0.00 & 0.97 &
        116.34 & \textbf{11.10}$^*$\\
        & 3 & 0.00 & 1.00 &
        139.58 & \textbf{0.31}$^*$\\
        & 10 & - & - &
        - & - \\
        \bottomrule
        \end{tabular}
        }
    \caption{Count-or-Memorization \vspace{.1cm} \label{tab:count-or-memnbrL}}
    \end{subtable}

    \begin{subtable}{1\linewidth}
        \centering
        \resizebox{0.65\textwidth}{!}{
        \begin{tabular}{lccccccccc}
        \toprule
        & & \multicolumn{3}{c}{FPA} &
        \multicolumn{3}{c}{$L$, nats} \\
        & $N_{Layer}$ & \texttt{add} &  \texttt{mul} & \texttt{mem} & \texttt{add} & \texttt{mul} & \texttt{mem} \\
        \midrule
        LSTM-s2s no att.
        & 1 & 0.00 & 0.94 & 0.00
        & 25.42 & \textbf{0.31}$^*$ & 57.32 \\
        & 3 & 0.15 & 0.20 & 0.00
        & \textbf{9.82} & 10.11 & 33.16 \\
        & 10 & 0.28 & 0.00 & 0.33
        & \textbf{5.83} & 23.16 & 10.01 \\
        \midrule
        LSTM-s2s att.
        & 1 & 0.00 & 0.98 & 0.00 &
        30.26 & \textbf{1.40}$^*$ & 58.84\\
        & 3 & 0.65 & 0.20 & 0.00 &
        \textbf{5.88}$^*$ & 15.67 & 27.82\\
        & 10 & 0.11 & 0.11 & 0.28
        & 9.66 & 27.72 & \textbf{8.26} \\
        \midrule
        CNN-s2s
        & 1 & 0.00 & 0.00 & 1.00 &
        318.12 & 346.19 & \textbf{0.00}$^*$ \\
        & 3 & 0.00 & 0.00 & 1.00 &
        1058.27 & 824.93 & \textbf{2.31}$^*$ \\
        & 10 & - & - & - &
        - & - & - \\
        \midrule
        Transformer
        & 1  & 0.00 & 0.00 & 1.00 &
        38.77 & 50.64 & \textbf{3.50}$^*$\\
        & 3 & 0.00 & 0.00 & 1.00 &
        40.03 & 57.73 & \textbf{0.18}$^*$\\
        & 10 & - & - & - &
        - & - & -\\
        \bottomrule
        \end{tabular}
    }
    \caption{Add-or-Multiply \vspace{.1cm}
    \label{tab:add-or-mulnbrL} }
    \end{subtable}

    \begin{subtable}{1\linewidth}
        \centering
        \resizebox{0.6\textwidth}{!}{
            \begin{tabular}{lccccccc}
            \toprule
            & & \multicolumn{2}{c}{FPA} &
            \multicolumn{2}{c}{$L$, nats}\\
            &  $N_{Layer}$ & \texttt{hierar} & \texttt{linear} &
            \texttt{hierar} & \texttt{linear} \\
            \midrule
            LSTM-s2s no att.
             & 1 & 0.05 & 0.00&
             \textbf{31.04}$^*$ & 61.84 \\

            & 3 & 0.00 & 0.00&
            \textbf{29.08}$^*$ & 50.92 \\%\textbf{7.27}$^*$ & 12.73 \\
            & 10 & - & -&
            - & - \\
            \midrule
            LSTM-s2s att.
            & 1 & 0.30 & 0.00 &
            \textbf{26.32}$^*$ & 57.20 \\
            & 3 & 0.00 & 0.00 &
             \textbf{32.32}$^*$ & 50.12 \\
            & 10 & - & -&
            - & - \\
            \midrule
            CNN-s2s
            & 1 & 0.00 & 1.00 &
            202.64 & \textbf{0.00}$^*$\\
            & 3 & 0.00 & 0.70 &
            222.32 & \textbf{1.84}$^*$ \\
            & 10 & - & -&
            - & - \\
            \midrule
            Transformer
            & 1 & 0.69 & 0.00 &
            \textbf{4.84}$^*$ & 35.04 \\%\textbf{1.21}$^*$ & 8.76\\
            & 3 & 0.56 & 0.00 &
            \textbf{5.48}$^*$ & 29.16 \\
            & 10 & - & -&
            - & - \\
            \bottomrule
            \end{tabular}
            }
    \caption{Hierarchical-or-Linear \vspace{.1cm}
    \label{tab:hierar-or-linearnbrL}}
    \end{subtable}

    \begin{subtable}{1\linewidth}
        \centering
        \resizebox{0.5\textwidth}{!}{
        \begin{tabular}{lcccccccc}
        \toprule
        & & \multicolumn{2}{c}{FPA} &
        \multicolumn{2}{c}{$L$, nats}  \\
         & $N_{Layer}$  & \texttt{comp} & \texttt{mem} &
         \texttt{comp} & \texttt{mem}\\
        \midrule
        LSTM-s2s no att.
        & 1 & 0.00 & 0.00 &
        42.65 & \textbf{38.55} \\
        & 3 & 0.00 & 0.00 &
        37.01 & \textbf{34.16} \\
        & 10 & - & - &
        - & - \\
        \midrule
        LSTM-s2s att.
        & 1 & 0.00 & 0.00 &
        \textbf{62.34}$^*$ & 70.92 \\
        & 3 & 0.00 & 0.00 &
        \textbf{46.10}$^*$ & 58.79 \\
        & 10 & - & - &
        - & - \\
        \midrule
        CNN-s2s
        & 1 & 0.75 & 0.00 &
        \textbf{1.44}$^*$ & 49.92 \\
        & 3 & 0.95 & 0.00 &
        \textbf{1.79}$^*$ & 66.44 \\
        & 10 & - & - &
        - & - \\
        \midrule
        Transformer
        & 1 & 0.00 & 0.00 &
        147.83 & \textbf{6.36}$^*$\\
        & 3 & - & - &
        - & -\\
        & 10 & - & - &
        - & - \\
        \bottomrule
        \end{tabular}
        }
    \caption{Composition-or-Memorization \label{tab:comp-or-memnbrL}}
    \end{subtable}

\caption{\textbf{Effect of the number of layers} ($N_{Layer}$): FPA measures the fraction of seeds that generalize according to a particular rule. Description length $L$ is averaged across examples and seeds. The lowest $L$ are in bold and $*$ denotes stat.\ sig.\ difference in  $L$ ($p < 10^{-2}$, paired t-test.). `-' denotes settings where learners have lower than $70\%$ success rate on the train set. \label{tab:nbrL}}

\end{table}

\subsection{Hidden size ($S_{Hidden}$)}
We experimented in the main text with standard seq2seq learners when hidden size $S_{Hidden}=512$. In this section, we look at the effect of $S_{Hidden}$ varying it in $\{128, 512, 1024\}$. We report learners performances in Table \ref{tab:hiddensize}.

First, Table \ref{tab:count-or-memHS} demonstrates how minor effect hidden size has on learners counting/memorization performances.
Indeed, for any given $S_{Hidden}$, between $84\%$ and $100\%$ of LSTM-based learners learn perfect counting after only one training example. Similarly, and with even a lower variation, more than $91\%$ of Transformer and CNN-s2s learners memorize the single training example outputting $b^{40}$ for any given $a^m$.

The same observation can be made when studying the interplay between the \texttt{hierar} and \texttt{linear} biases (Table \ref{tab:hierar-or-linearHS}) and \texttt{comp} and \texttt{mem} biases (Table~\ref{tab:comp-or-memHS}). Concretely, Tables \ref{tab:hierar-or-linearHS} and~\ref{tab:comp-or-memHS} show

that learners' generalizations are stable across $S_{Hidden}$ values with the exception of LSTM-based learners that loose significance for some tested $S_{Hidden}$ values. Yet, there is no switch of preference.

Finally, as demonstrated in Table \ref{tab:add-or-mulHS}, \textit{all} Transformer and CNN-s2s learners perform perfect memorization when tested on the \textit{Add-or-Multiply} task independently of their hidden sizes. Both LSTM-based learners are significantly biased toward \texttt{mul} for  $S_{Hidden} \in \{512, 1024\}$. However, when experimenting with smaller $S_{Hidden}$ (=128), we detect a switch of preference for LSTM-s2s no att.\ learners. The latter start approximating \texttt{add}-type rule (with significantly lower $L$). Lastly, we do not distinguish any significant difference between \texttt{add} and \texttt{mul} for LSTM-s2s att.\ when  $S_{Hidden}=128$.

Taken together, learners' biases are quite robust to $S_{Hidden}$ variations. We however note a switch of preference from \texttt{mul} to \texttt{add} for LSTM-s2s no att.\ learners when decreasing $S_{Hidden}$. Furthermore, we see a loss of significant preference in five distinct settings.

\begin{table}
\centering
\captionsetup[subtable]{position = below}

    \begin{subtable}{1\linewidth}
        \centering
        \resizebox{0.5\textwidth}{!}{
        \begin{tabular}{lcccccccc}
        \toprule
        & & \multicolumn{2}{c}{FPA} &
        \multicolumn{2}{c}{$L$, nats}  \\
         & $S_{Hidden}$ & \texttt{count} & \texttt{mem} &
         \texttt{count} & \texttt{mem}\\
        \midrule
        LSTM-s2s no att.
        & 128 & 0.84 & 0.00 &
        \textbf{8.25}$^*$ & 109.84 \\
        & 512 & 1.00 & 0.00 &
        \textbf{0.01}$^*$ & 97.51 \\
        & 1024 & 1.00 & 0.00 &
        \textbf{0.00}$^*$ & 149.86 \\
        \midrule
        LSTM-s2s att.
        & 128 & 0.90 & 0.00
        & \textbf{0.01}$^*$ & 89.31   \\
        & 512 & 0.99 & 0.00 &
        \textbf{7.84}$^*$ & 121.48 \\
        & 1024 & 1.00 & 0.00 &
        \textbf{0.00}$^*$ & 300.93 \\
        \midrule
        CNN-s2s
        & 128 & 0.00 & 1.00 &
        805.01 & \textbf{0.00}$^*$ \\
        & 512 & 0.00 & 0.98 &
        660.73 & \textbf{0.02}$^*$ \\
        & 1024 & 0.00 & 1.00 &
        993.85 & \textbf{0.00}$^*$ \\
        \midrule
        Transformer
        & 128 & 0.00 & 0.91 &
        110.68 & \textbf{9.57}$^*$\\
        & 512 & 0.00 & 0.97 &
        116.34 & \textbf{11.10}$^*$\\
        & 1024 & 0.00 & 0.94 &
        122.38 & \textbf{1.42}$^*$\\
        \bottomrule
        \end{tabular}
        }
    \caption{Count-or-Memorization \vspace{.1cm}
    \label{tab:count-or-memHS}}
    \end{subtable}

    \begin{subtable}{1\linewidth}
        \centering
        \resizebox{0.65\textwidth}{!}{
        \begin{tabular}{lccccccccc}
        \toprule
        & & \multicolumn{3}{c}{FPA} &
        \multicolumn{3}{c}{$L$, nats} \\
        & $S_{Hidden}$ & \texttt{add} &  \texttt{mul} & \texttt{mem} & \texttt{add} & \texttt{mul} & \texttt{mem} \\
        \midrule
        LSTM-s2s no att.
        & 128 & 0.00 & 0.00 & 0.00
        & \textbf{7.56}$^*$ & 19.66 & 43.72 \\
        & 512 & 0.00 & 0.94 & 0.00
        & 25.42 & \textbf{0.31}$^*$ & 57.32 \\
        & 1024 & 0.25 & 0.75 & 0.00
        & 30.29 & \textbf{5.26}$^*$ & 77.99 \\
        \midrule
        LSTM-s2s att.
        & 128 & 0.00 & 0.00 & 0.00 &
        \textbf{15.32} & 17.37  & 45.09\\
        & 512 & 0.00 & 0.98 & 0.00 &
        30.26 & \textbf{1.40}$^*$ & 58.84\\
        & 1024 & 0.00 & 1.00 & 0.00
        & 51.70 & \textbf{3.09}$^*$ & 86.82 \\
        \midrule
        CNN-s2s
        & 128 & 0.00 & 0.00 & 1.00 &
        281.34 & 301.75 & \textbf{0.02}$^*$ \\
        & 512 & 0.00 & 0.00 & 1.00 &
        318.12 & 346.19 & \textbf{0.00}$^*$ \\
        & 1024 & 0.00 & 0.00 & 1.00 &
        520.75 & 508.75 & \textbf{0.00}$^*$ \\
        \midrule
        Transformer
        & 128 & 0.00 & 0.00 & 1.00 &
        35.21 & 46.07 & \textbf{2.94}$^*$\\
        & 512 & 0.00 & 0.00 & 1.00 &
        38.77 & 50.64 & \textbf{3.50}$^*$\\
        & 1024 & 0.00 & 0.00 & 1.00 &
        38.74 & 51.71 & \textbf{0.88}$^*$\\
        \bottomrule
        \end{tabular}
    }
    \caption{Add-or-Multiply \vspace{.1cm}
    \label{tab:add-or-mulHS} }
    \end{subtable}

    \begin{subtable}{1\linewidth}
        \centering
        \resizebox{0.65\textwidth}{!}{
            \begin{tabular}{lccccccc}
            \toprule
            & & \multicolumn{2}{c}{FPA} &
            \multicolumn{2}{c}{$L$, nats}\\
            & $S_{Hidden}$ & \texttt{hierar} & \texttt{linear} &
            \texttt{hierar} & \texttt{linear} \\
            \midrule
            LSTM-s2s no att.
             & 128 & 0.00 & 0.00&
        \textbf{30.40}$^*$ & 79.00 \\%\textbf{7.60}$^*$ & 19.75 \\
            & 512 & 0.05 & 0.00&
            \textbf{31.04}$^*$ & 61.84 \\%\textbf{7.76}$^*$ & 15.46 \\
            & 1024 & 0.00 & 0.00&
            60.24 & \textbf{47.24} \\
            \midrule
            LSTM-s2s att.
            & 128 & 0.00 & 0.00 &
            \textbf{32.72}$^*$ & 72.28\\% \textbf{8.18}$^*$ & 18.07 \\
            & 512 & 0.30 & 0.00 &
            \textbf{26.32}$^*$ & 57.2 \\
            & 1024 & 0.05 & 0.00&
            \textbf{65.80} & 73.80 \\
            \midrule
            CNN-s2s
            & 128 & 0.00 & 0.95 &
            178.88 & \textbf{0.00}$^*$ \\
            & 512 & 0.00 & 1.00 &
            202.64 & \textbf{0.00}$^*$ \\
            & 1024 & 0.00 & 0.95 &
            225.36 & \textbf{0.12}$^*$ \\

            \midrule
            Transformer
            & 128 & 0.75 & 0.00 &
            \textbf{2.96}$^*$ & 36.92 \\

            & 512 & 0.69 & 0.00 &
            \textbf{4.84}$^*$ & 35.04 \\
            & 1024 & 0.75 & 0.00&
            \textbf{31.04}$^*$ & 61.84 \\
            \bottomrule
            \end{tabular}
            }
    \caption{Hierarchical-or-Linear\vspace{.1cm}
    \label{tab:hierar-or-linearHS}}
    \end{subtable}

    \begin{subtable}{1\linewidth}
        \centering
        \resizebox{0.5\textwidth}{!}{
        \begin{tabular}{lcccccccc}
        \toprule
        & & \multicolumn{2}{c}{FPA} &
        \multicolumn{2}{c}{$L$, nats}  \\
         & $S_{Hidden}$   & \texttt{comp} & \texttt{mem} &
         \texttt{comp} & \texttt{mem}\\
        \midrule
        LSTM-s2s no att.
        & 128 & 0.00 & 0.00 &
        \textbf{37.67}$^*$ & 58.52 \\
        & 512 & 0.00 & 0.00 &
        42.65 & \textbf{38.55} \\
        & 1024 & 0.00 & 0.00 &
        \textbf{37.66}$^*$ & 79.71 \\
        \midrule
        LSTM-s2s att.
        & 128 & 0.00 & 0.00 &
        66.65 & \textbf{63.84} \\
        & 512 & 0.00 & 0.00 &
        \textbf{62.34}$^*$ & 70.92 \\
        & 1024 & 0.00 & 0.00 &
        \textbf{42.38}$^*$ & 73.28 \\
        \midrule
        CNN-s2s
        & 128 & 0.85 & 0.00 &
        \textbf{0.99}$^*$ & 53.38 \\
        & 512 & 0.75 & 0.00 &
        \textbf{1.44}$^*$ & 49.92 \\
        & 1024 & 0.80 & 0.00 &
        \textbf{1.24}$^*$ & 54.86 \\
        \midrule
        Transformer
        & 128 & 0.00 & 0.66 &
        155.50 & \textbf{6.23}$^*$\\
        & 512 & 0.00 & 0.00 &
        147.83 & \textbf{6.36}$^*$\\
        & 1024 & 0.00 & 0.60 &
        151.70 & \textbf{6.02}$^*$\\
        \bottomrule
        \end{tabular}
        }
    \caption{Composition-or-Memorization \label{tab:comp-or-memHS}}
    \end{subtable}

\caption{\textbf{Effect of the hidden size} ($S_{Hidden}$): FPA measures the fraction of seeds that generalize according to a particular rule. Description length $L$ is averaged across examples and seeds. The lowest $L$ are in bold and $*$ denotes stat.\ sig.\ difference in  $L$ ($p < 10^{-2}$, paired t-test).\label{tab:hiddensize}}
\end{table}

\subsection{Embedding size ($S_{Emb}$)}

We look here at the effect of the embedding size, $S_{Emb}$, on learners' generalizations. In particular, we vary $S_{Emb} \in \{16,64,256\}$. Results are reported in Table \ref{tab:embed}.

Across sub-tables~\ref{tab:count-or-memEmbd}, \ref{tab:add-or-mulEmbd} and \ref{tab:hierar-or-linearEmbd}, we see small influence of $S_{Emb}$ on learners' biases. For example, if we consider the \textit{Count-or-Memorization} task when varying $S_{Emb}$ (see Table \ref{tab:count-or-memEmbd}), between $95\%$ and $100\%$ of LSTM-s2s no att.\ learners inferred perfectly the \texttt{count} hypothesis. More striking, between $99\%$ and $100\%$ of  LSTM-s2s att.\ learners learned the \texttt{count} rule after one training example. The same trend is observed for the remaining learners and

across the other tasks; \textit{Add-or-Multiply} (Table \ref{tab:add-or-mulEmbd})  and \textit{Hierarchical-or-Linear} (Table \ref{tab:hierar-or-linearEmbd}). Yet, we still discern in some cases, systematic, but low, effects of $S_{Emb}$. First, the larger $S_{Emb}$ is, the lower  FPA-\texttt{mul} of LSTM-s2s no att.\ learners is (from 0.94 for $S_{Emb}=16$ to 0.84 for $S_{Emb}=256$).
However, LSTM-s2s no att.\ learners still have considerable preference for \texttt{mul} for any tested $S_{Emb}$. Second, we see an increase of Transformer's preference for \texttt{hierar} with the increase of $S_{Emb}$. Surprisingly, for $S_{Emb} \geq 64$, $100\%$ of Transformer learners generalize to perfect \texttt{hierar} hypothesis.

Finally, when considering the \textit{Composition-or-Memorization} task, we observe in Table~\ref{tab:comp-or-memembed}, for all learners, a tendency to prefer \texttt{comp} generalization when $S_{Emb}$ is large. For example, if, for LSTM-based learners, we note $0.00$ \texttt{comp}-FPA when $S_{Emb}=16$, \texttt{comp}-FPA$\geq 0.85$ with $S_{Emb}=256$. Interestingly, Transformers switch their preference, showing a significant bias toward compositional reasoning with $S_{Emb}=256$.

\begin{table}
\centering
\captionsetup[subtable]{position = below}

    \begin{subtable}{1\linewidth}
        \centering
        \resizebox{0.5\textwidth}{!}{
        \begin{tabular}{lcccccccc}
        \toprule
        & & \multicolumn{2}{c}{FPA} &
        \multicolumn{2}{c}{$L$, nats}  \\
         & $S_{Emb}$ & \texttt{count} & \texttt{mem} &
         \texttt{count} & \texttt{mem}\\
        \midrule
        LSTM-s2s no att.
        & 16 & 1.00 & 0.00 &
        \textbf{0.01}$^*$ & 97.51 \\
        & 64 & 0.95 & 0.00 &
        \textbf{0.00}$^*$ & 91.54 \\
        & 256 & 1.00 & 0.00 &
        \textbf{0.00}$^*$ & 90.32 \\
        \midrule
        LSTM-s2s att.
        & 16 & 0.99 & 0.00 &
        \textbf{7.84}$^*$ & 121.48 \\
        & 64 & 1.00 & 0.00 &
        \textbf{11.12}$^*$ & 117.39 \\
        & 256 & 1.00 & 0.00 &
        \textbf{9.79}$^*$ & 127.31 \\
        \midrule
        CNN-s2s
        & 16 & 0.00 & 0.98 &
        660.73 & \textbf{0.02}$^*$ \\
        & 64 & 0.00 & 1.00 &
        670.53 & \textbf{0.00}$^*$ \\
        & 256 & 0.00 & 0.95 &
        826.23 & \textbf{0.01}$^*$ \\
        \midrule
        Transformer
        & 16 & 0.00 & 0.97 &
        116.34 & \textbf{11.10}$^*$\\
        & 64 & 0.00 & 1.00 &
        232.53 & \textbf{0.00}$^*$\\
        & 256 & 0.00 & 1.00 &
        338.88 & \textbf{0.00}$^*$\\
        \bottomrule
        \end{tabular}
        }
    \caption{Count-or-Memorization \vspace{.1cm}
    \label{tab:count-or-memEmbd}}
    \end{subtable}

    \begin{subtable}{1\linewidth}
        \centering
        \resizebox{0.65\textwidth}{!}{
        \begin{tabular}{lccccccccc}
        \toprule
        & & \multicolumn{3}{c}{FPA} &
        \multicolumn{3}{c}{$L$, nats} \\
        & $S_{Emb}$ & \texttt{add} &  \texttt{mul} & \texttt{mem} & \texttt{add} & \texttt{mul} & \texttt{mem} \\
        \midrule
        LSTM-s2s no att.
        & 16 & 0.00 & 0.94 & 0.00
        & 25.42 & \textbf{0.31}$^*$ & 57.32 \\
        & 64 & 0.05 & 0.90 & 0.00
        & 23.70 & \textbf{1.41}$^*$ & 51.33 \\
        & 256 & 0.05 & 0.84 & 0.00
        & 20.42 & \textbf{1.33}$^*$ & 51.34 \\
        \midrule
        LSTM-s2s att.
        & 16 & 0.00 & 0.98 & 0.00 &
        30.26 & \textbf{1.40}$^*$ & 58.84\\
        & 64 & 0.07 & 0.93 & 0.00 &
        26.71 & \textbf{2.54}$^*$ & 50.65\\
        & 256 & 0.00 & 1.00 & 0.00
        & 26.83 & \textbf{1.94}$^*$ & 51.20 \\
        \midrule
        CNN-s2s
        & 16 & 0.00 & 0.00 & 1.00 &
        318.12 & 346.19 & \textbf{0.00}$^*$ \\
        & 64 & 0.00 & 0.00 & 1.00 &
        293.86 &294.50 & \textbf{0.00}$^*$ \\
        & 256 & 0.00 & 0.00 & 1.00 &
        486.81 & 447.20 & \textbf{0.00}$^*$ \\
        \midrule
        Transformer
        & 16  & 0.00 & 0.00 & 1.00 &
        38.77 & 50.64 & \textbf{3.50}$^*$\\
        & 64 & 0.00 & 0.00 & 1.00 &
        87.11 & 142.83 & \textbf{0.00}$^*$\\
        & 256 & 0.00 & 0.00 & 1.00 &
        118.34 & 172.65 & \textbf{0.00}$^*$\\
        \bottomrule
        \end{tabular}
    }
    \caption{Add-or-Multiply \vspace{.1cm}
    \label{tab:add-or-mulEmbd} }
    \end{subtable}

    \begin{subtable}{1\linewidth}
        \centering
        \resizebox{0.6\textwidth}{!}{
            \begin{tabular}{lccccccc}
            \toprule
            & & \multicolumn{2}{c}{FPA} &
            \multicolumn{2}{c}{$L$, nats}\\
            & $S_{Emb}$ & \texttt{hierar} & \texttt{linear} &
            \texttt{hierar} & \texttt{linear} \\
            \midrule
            LSTM-s2s no att.
             & 16 & 0.05 & 0.00&
             \textbf{31.04}$^*$ & 61.84 \\

            & 64 & 0.10 & 0.00&
        \textbf{34.44}$^*$ & 72.2 \\
            & 256 & 0.00 & 0.00 &
            \textbf{36.32} & 76.56 \\

            \midrule
            LSTM-s2s att.
            & 16 & 0.30 & 0.00 &
            \textbf{26.32}$^*$ & 57.2 \\
            & 64 & 0.30 & 0.00 &
            \textbf{23.4} & 72.68 \\
            & 256 & 0.05 & 0.00&
            \textbf{55.56}$^*$ & 90.76 \\
            \midrule
            CNN-s2s
            & 16 & 0.00 & 1.00 &
            202.64 &
            \textbf{0.00}$^*$\\
            & 64 & 0.00 & 1.00 &

            227.12 &
            \textbf{0.08}$^*$\\

            & 256 & 0.00 & 0.94 &
            419.28 & \textbf{8.84}$^*$ \\

            \midrule
            Transformer
            & 16 & 0.69 & 0.00 &
            \textbf{4.84}$^*$ & 35.04 \\

            & 64 & 1.00 & 0.00 &
            \textbf{0.00}$^*$
            & 81.16 \\

            & 256 & 1.00 & 0.00&
            \textbf{0.56}$^*$ & 121.68 \\

            \bottomrule
            \end{tabular}
            }
    \caption{Hierarchical-or-Linear \vspace{.1cm}
    \label{tab:hierar-or-linearEmbd}}
    \end{subtable}

    \begin{subtable}{1\linewidth}
        \centering
        \resizebox{0.5\textwidth}{!}{
        \begin{tabular}{lcccccccc}
        \toprule
        & & \multicolumn{2}{c}{FPA} &
        \multicolumn{2}{c}{$L$, nats}  \\
         & $S_{Emb}$  & \texttt{comp} & \texttt{mem} &
         \texttt{comp} & \texttt{mem}\\
        \midrule
        LSTM-s2s no att.
        & 16 & 0.00 & 0.00 &
        42.65 & \textbf{38.55} \\
        & 64 & 0.95 & 0.00 &
        \textbf{0.11}$^*$ & 31.44 \\
        & 256 & 0.95 & 0.00 &
        \textbf{2.12}$^*$ & 23.63 \\
        \midrule
        LSTM-s2s att.
        & 16 & 0.00 & 0.00 &
        \textbf{62.34}$^*$ & 70.92 \\
        & 64 & 0.95 & 0.00 &
        \textbf{0.36}$^*$ & 47.57 \\
        & 254 & 0.85 & 0.00 &
        \textbf{0.86}$^*$ & 49.39\\
        \midrule
        CNN-s2s
        & 16 & 0.75 & 0.00 &
        \textbf{1.44}$^*$ & 49.92 \\
        & 64 & 1.00 & 0.00 &
        \textbf{0.01}$^*$ & 112.09 \\
        & 256 & 0.95 & 0.00 &
        \textbf{0.18}$^*$ & 139.51 \\
        \midrule
        Transformer
        & 16 & 0.00 & 0.00 &
        147.83 & \textbf{6.36}$^*$\\
        & 64 & 0.00 & 0.00 &
        103.25 & \textbf{69.07}$^*$\\
        & 256 & 0.10 & 0.00 &
        \textbf{70.76}$^*$ & 107.54 \\
        \bottomrule
        \end{tabular}
        }
    \caption{Composition-or-Memorization \label{tab:comp-or-memembed}}
    \end{subtable}
\caption{\textbf{Effect of the embedding size ($S_{Emb}$)}: FPA measures the fraction of seeds that generalize according to a particular rule. Description length $L$ is averaged across examples and seeds. The lowest $L$ are in bold and $*$ denotes stat.\ sig.\ difference in  $L$ ($p < 10^{-2}$, paired t-test).\label{tab:embed}}
\end{table}

\bigskip
In this section, we studied the impact of the number of layers, hidden and embedding sizes on learners' generalizations. We found that, if these hyper-parameters can influence, in some cases, the degree of one learner's preference w.r.t.\ a given rule, inductive biases are quite robust to their changes. In particular, among all tested combinations, we observe only $3$ cases of preference switch (out of $136$).

\section{Robustness to changes in training parameters}
\label{sec:hyperparam_training}
We examine here the effect of the training parameters on learners' biases. As previously, we only consider the \textit{Count-or-Memorization} task with $l=40$, the \textit{Add-or-Multiply} task with $l=20$, the  \textit{Hierarchical-or-Linear} task with $d=4$ and the \textit{Composition-or-Memorization} task with $M=36$. We experiment with the architectures detailed in the main text; however, we use 20 different random seeds instead of 100.

We consider in  this section two different hyperparameters: (1) the choice of the optimizer, and (2) the dropout probability.

\textbf{Optimizer} We experiment with replacing the Adam optimizer~\citep{kingma2014} with SGD~\citep{bottou2018}.
We found experimentally  that learners failed to learn the training examples consistently in most of the settings. Yet, when successful, they showed the same preferences. In particular, Transformer and CNN-s2s were the only learners that had good performances on \textit{Count-or-Memorization} and \textit{Add-or-Multiply} train sets (success rate higher than $70\%$). These learners showed a prefect generalization to the \texttt{mem} rule in both tasks. Prior works had shown that SGD leads to better generalization compared to other adaptive variants~\citep{Wilson:etal:2017}. However, based on our few successful instances with SGD, we do not observe a difference between SGD and Adam results. One main difference compared to the prior work is the definition of generalization. For instance, in the \textit{Count-or-Memorization} task, memorizing the training example could be seen as a perfect generalization as it explains the training set fully. Hence, preferring memorization when trained with SGD, as opposed  to counting, does not contradict the advantage of SGD when testing generalization performances.

\textbf{Dropout} We then examine how the dropout probability affects learners' preferences. We use, as mentioned in the main paper, Adam optimizer and vary the dropout probability $dropout \in \{0.0, 0.2, 0.5\}$. Results are reported in Table \ref{tab:dropout}.

Both \textit{Count-or-Memorization} (Table~\ref{tab:count-or-memdropout}) and \textit{Add-or-Multiply} (Table~\ref{tab:add-or-muldropout}) tasks show the same trend. First, Transformer and CNN-s2s learners prefer consistently the \texttt{mem} rule.
Second, when looking at LSTM-based learners, we distinguish a more complex behavior. For $dropout \geq 0.2$, LSTM-based learners show a significant preference for arithmetic reasoning (\texttt{count} for the  \textit{Count-or-Memorization} task and  \texttt{mul} for the  \textit{Add-or-Multiply} task). However, when $dropout=0.0$, we see different preferences. In particular, both LSTM-based learners show a preference for \texttt{mem} (not significant for LSTM-s2s att.), LSTM-s2s no att.\ learners are significantly biased toward \texttt{add} whereas LSTM-s2s att.\ do not show any significant bias with a slight preference for \texttt{mem}. In sum, the lower $dropout$ is,  the more likely learners will overfit the \texttt{mem} rule.

The same observation holds for the \textit{Composition-or-Memorization} task in Table~\ref{tab:comp-or-memdropout}. That is, $dropout$ has no impact on CNN-s2s and Transformer biases (the former show a significant preference for \texttt{comp} while the latter prefers \texttt{mem} for any tested $dropout$ value), but does impact LSTM-based learners' biases, such as a $dropout=0.0$ favors memorization.

Finally, we consider the \textit{Hierarchical-or-Linear} task (see Table~\ref{tab:hierar-or-lineardropout}). We observe that, for any $dropout$ value, CNN-s2s and Transformer inductive biases remain the same. Indeed, CNN-s2s learners show a consistent preference for \texttt{linear} with  FPA$\geq 0.75$ while Transformers prefer \texttt{hierar} (note that this preference is not very large for $dropout=0.0$ with an FPA-\texttt{hierar} of 0.05, compared to an FPA-\texttt{hierar} of 1.00 and 0.69 for $dropout=0.2$ and $0.5$ respectively). On the other hand, $dropout$ has a larger impact on LSTM-based learners. When $dropout=0.5$, both LSTM-s2s prefer the \texttt{hierar} hypothesis. However, for  $dropout=0.0$, both learners do not show any significant preference for any of the rules (with $0$ FPA for both rules and close $L$ values).

\begin{table}
\centering
\captionsetup[subtable]{position = below}

    \begin{subtable}{1\linewidth}
        \centering
        \resizebox{0.5\textwidth}{!}{
        \begin{tabular}{lcccccccc}
        \toprule
        & & \multicolumn{2}{c}{FPA} &
        \multicolumn{2}{c}{$L$, nats}  \\
         & $dropout$ & \texttt{count} & \texttt{mem} &
         \texttt{count} & \texttt{mem}\\
        \midrule
        LSTM-s2s no att.
        & 0.0 & 0.00 & 0.20 &
        56.23 & \textbf{16.52}$^*$ \\
        & 0.2 & 0.95 & 0.00 &
        \textbf{0.17}$^*$ & 60.15 \\
        & 0.5 & 1.00 & 0.00 &
        \textbf{0.01}$^*$ & 97.51 \\
        \midrule
        LSTM-s2s att.
        & 0.0 & 0.32 & 0.68 &
        63.30 & \textbf{47.68}  \\
        & 0.2 & 0.95 & 0.05 &
        \textbf{33.66}$^*$ & 87.36 \\
        & 0.0 & 0.99 & 0.00 &
        \textbf{7.84}$^*$ & 121.48 \\
        \midrule
        CNN-s2s
        & 0.0 & 0.00 & 0.55 &
        1034.67 & \textbf{0.43}$^*$ \\
        & 0.2 & 0.00 & 0.98 &
        999.62 & \textbf{0.01}$^*$ \\
        & 0.5 & 0.00 & 0.98 &
        660.73 & \textbf{0.02}$^*$ \\
        \midrule
        Transformer
        & 0.0 & 0.00 & 0.65 &
        261.02 & \textbf{1.17}$^*$\\
        & 0.2 & 0.00 & 1.00 &
        171.31 & \textbf{0.05}$^*$\\
        & 0.5 & 0.00 & 0.97 &
        116.34 & \textbf{11.10}$^*$\\
        \bottomrule
        \end{tabular}
        }
    \caption{Count-or-Memorization \vspace{.1cm}
    \label{tab:count-or-memdropout}}
    \end{subtable}

    \begin{subtable}{1\linewidth}
        \centering
        \resizebox{0.65\textwidth}{!}{
        \begin{tabular}{lccccccccc}
        \toprule
        & & \multicolumn{3}{c}{FPA} &
        \multicolumn{3}{c}{$L$, nats} \\
        & $dropout$ & \texttt{add} &  \texttt{mul} & \texttt{mem} & \texttt{add} & \texttt{mul} & \texttt{mem} \\
        \midrule
        LSTM-s2s no att.
        & 0.0 & 0.25 & 0.00 & 0.00
        & \textbf{5.00}$^*$ & 35.55 & 19.07 \\
        & 0.2 & 0.30 & 0.45 & 0.00
        & 12.07 & \textbf{11.04} & 37.39 \\
        & 0.5 & 0.00 & 0.94 & 0.00
        & 25.42 & \textbf{0.31}$^*$ & 57.32 \\
        \midrule
        LSTM-s2s att.
        & 0.0 & 0.00 & 0.11 & 0.58 &
        25.09 & 36.33 & \textbf{12.09}\\
        & 0.2 & 0.18 & 0.53 & 0.18 &
        22.22 & \textbf{9.92}$^*$ & 34.48\\
        & 0.5 & 0.00 & 0.98 & 0.00 &
        30.26 & \textbf{1.40}$^*$ & 58.84\\
        \midrule
        CNN-s2s
        & 0.0 & 0.00 & 0.00 & 0.65 &
        236.41 & 247.52 & \textbf{0.42}$^*$ \\
        & 0.2 & 0.00 & 0.00 & 1.00 &
        438.06 & 464.26 & \textbf{0.00}$^*$ \\
        & 0.5 & 0.00 & 0.00 & 1.00 &
        318.12 & 346.19 & \textbf{0.00}$^*$ \\
        \midrule
        Transformer
        & 0.0  & 0.00 & 0.00 & 0.65 &
        84.58 & 130.88 & \textbf{0.96}$^*$\\
        & 0.2  & 0.00 & 0.00 & 1.00 &
        65.62 & 99.05 & \textbf{0.02}$^*$\\
        & 0.5  & 0.00 & 0.00 & 1.00 &
        38.77 & 50.64 & \textbf{3.50}$^*$\\
        \bottomrule
        \end{tabular}
    }
    \caption{Add-or-Multiply \vspace{.1cm}
    \label{tab:add-or-muldropout} }
    \end{subtable}

    \begin{subtable}{1\linewidth}
        \centering
        \resizebox{0.6\textwidth}{!}{
            \begin{tabular}{lccccccc}
            \toprule
            & & \multicolumn{2}{c}{FPA} &
            \multicolumn{2}{c}{$L$, nats}\\
            & $dropout$ & \texttt{hierar} & \texttt{linear} &
            \texttt{hierar} & \texttt{linear} \\
            \midrule
            LSTM-s2s no att.
             & 0.0 & 0.00 & 0.00&
            \textbf{16.38} & 17.72 \\
            & 0.2 & 0.00 & 0.00&
            \textbf{11.09}$^*$ & 19.87 \\
            & 0.5 & 0.05 & 0.00&
            \textbf{7.76}$^*$ & 15.46 \\
            \midrule
            LSTM-s2s att.
            & 0.0 & 0.00 & 0.00 &
            31.12 & \textbf{28.61} \\
            & 0.2 & 0.00 & 0.00 &
            \textbf{10.63} & 17.55 \\
            & 0.5 & 0.30 & 0.00 &
            \textbf{6.58}$^*$ & 14.30 \\
            \midrule
            CNN-s2s
            & 0.0 & 0.00 & 0.75 &
            68.48 & \textbf{0.44}$^*$\\
            & 0.2 & 0.00 & 1.00 &
            99.42 & \textbf{1.16}$^*$\\
            & 0.5 & 0.00 & 1.00 &
            50.66 & \textbf{0.00}$^*$\\
            \midrule
            Transformer
            & 0.0 & 0.05 & 0.00 &
            \textbf{3.99}$^*$ & 8.56\\
            & 0.2 & 1.00 & 0.00 &
            \textbf{0.09}$^*$ & 13.09\\
            & 0.5 & 0.69 & 0.00 &
            \textbf{1.21}$^*$ & 8.76\\
            \bottomrule
            \end{tabular}
            }
    \caption{Hierarchical-or-Linear \vspace{.1cm}
    \label{tab:hierar-or-lineardropout}}
    \end{subtable}

    \begin{subtable}{1\linewidth}
        \centering
        \resizebox{0.5\textwidth}{!}{
        \begin{tabular}{lcccccccc}
        \toprule
        & & \multicolumn{2}{c}{FPA} &
        \multicolumn{2}{c}{$L$, nats}  \\
         & $dropout$  & \texttt{comp} & \texttt{mem} &
         \texttt{comp} & \texttt{mem}\\
        \midrule
        LSTM-s2s no att.
        & 0.0 & 0.00 & 0.00 &
        32.66 & \textbf{11.15}$^*$ \\
        & 0.2 & 0.30 & 0.00 &
        \textbf{6.42} & 11.01 \\
        & 0.5 & 0.00 & 0.00 &
        42.65 & \textbf{38.55} \\
        \midrule
        LSTM-s2s att.
        & 0.0 & 0.00 & 0.00 &
        22.24 & \textbf{10.93}$^*$ \\
        & 0.2 & 0.45 & 0.00 &
        \textbf{4.38}$^*$ & 35.14 \\
        & 0.5 & 0.00 & 0.00 &
        \textbf{62.34}$^*$ & 70.92 \\
        \midrule
        CNN-s2s
        & 0.0 & 0.30 & 0.00 &
        \textbf{53.00}$^*$ & 92.06 \\
        & 0.2 & 0.75 & 0.00 &
        \textbf{0.37}$^*$ & 110.50 \\
        & 0.5 & 0.75 & 0.00 &
        \textbf{1.44}$^*$ & 49.92 \\
        \midrule
        Transformer
        & 0.0 & 0.00 & 0.05 &
        129.65 & \textbf{27.12}$^*$\\
        & 0.2 & 0.00 & 0.00 &
        102.90 & \textbf{27.56}$^*$\\
        & 0.5 &  0.00 & 0.00 &
        147.83 & \textbf{6.36}$^*$\\
        \bottomrule
        \end{tabular}
        }
    \caption{Composition-or-Memorization \label{tab:comp-or-memdropout}}
    \end{subtable}
\caption{\textbf{Effect of dropout probability}: FPA measures the fraction of seeds that generalize according to a particular rule. Description length $L$ is averaged across examples and seeds. The lowest $L$ are in bold and $*$ denotes stat.\ sig.\ difference in  $L$ ($p < 10^{-2}$, paired t-test).\label{tab:dropout}}
\end{table}

\section{SCAN}

\begin{figure*}[tb]
  \centering
  \resizebox{0.8\textwidth}{!}{
  \begin{tabular}{lll}
    jump&$\Rightarrow$&JUMP\\

    jump around right&$\Rightarrow$&RTURN JUMP RTURN JUMP RTURN JUMP RTURN JUMP\\
    turn left twice&$\Rightarrow$&LTURN LTURN\\

     jump opposite left after walk around left&$\Rightarrow$&LTURN WALK LTURN WALK LTURN WALK LTURN WALK LTURN LTURN JUMP\\
  \end{tabular}
  }
  \caption{Examples of SCAN trajectories and instructions, adopted from \citep{Lake2017}.}
  \label{fig:scan-examples}
\end{figure*}

In the main text, we studied preferences of the learners towards compositional generalization in the \textit{Composition-or-Memorization} task. Here, we resort to a larger-scale SCAN task~\citep{Lake2017}, which can be thought of as a generalization of \textit{Composition-or-Memorization} with multiple modifiers.
In SCAN, inputs are sequences that represent trajectories and outputs are step-wise instructions for following these instructions (see Figure~\ref{fig:scan-examples}).
We experiment with the SCAN-jump split of the dataset, where the test set (7706 examples) is obtained by filtering all compositional uses of one of the primitives, \texttt{jump}. The train set (14670 examples) contains all uses of all other primitives (including compositional), and lines where \texttt{jump} occurs in isolation  (only as a primitive). This makes the training data ambiguous only for the \texttt{jump} instruction. However, learners can transfer compositional rules across the primitives. We refer to this split simply as SCAN.

We consider two generalizations: (1) all input sequences with \texttt{jump} are mapped to a single instruction \texttt{JUMP} as memorized from the training examples, or (2) underlying compositional grammar. We call them \texttt{mem} and \texttt{comp}, respectively. We used the original test as a representative of the \texttt{comp} candidate explanation and generated one for \texttt{mem} ourselves.

Recently, \cite{Hupkes2020} compared how
different seq2seq learners perform on a context-free grammar, similar to SCAN, that requires compositional reasoning. Their work aims to study if and how learners pick up the underlying rules in the data. In contrast, our setup allows investigating learners' preferences. In particular, we apply the description length metric to investigate learners' biases toward the \texttt{mem} and \texttt{comp} rules that explain the training examples in our setup.

\paragraph{Sequence-to-sequence learners}

We use the following models when experimenting with SCAN:\\
\textbf{LSTM-s2s}: We chose the architecture used in~\cite{Lake2017}. In particular, Encoder and Decoder are  two hidden layers with 200 units and embedding of dimension 32. This architecture gets 0.98 test accuracy on the i.i.d.\ (simple) split of SCAN, averaged over 10 seeds.\\
\textbf{CNN-s2s}: We use one of the successful CNN-s2s models of \cite{Dessi2019} that has 5 layers and embedding size of  128. We also vary kernel size in $\{3,5,8\}$ as it was found to impact the performance on SCAN~\citep{Dessi2019}. These architectures reach test accuracy above 0.98 on the i.i.d.\ split of SCAN, averaged over 10 seeds.\\
\textbf{Transformer}: We believe our work is the first study of Transformer's performance on SCAN. For both Encoder and Decoder, we use 8 attention heads, 4 layers, embedding size of 64, FFN layer dimension of 256. This architecture gets 0.94 test accuracy on the i.i.d.\ split of SCAN, averaged over 10 seeds.

\paragraph{Training and evaluation}
We follow the same scenario described in the main paper with two differences: (a) when calculating $L$, we use blocks of size 1024, (b) during training, we sample $10^4$ batches with replacement, similar to~\citep{Lake2017}. We use batches of size 16 for LSTM-s2s \& CNN-s2s, and 256 for Transformer. We repeat the training/evaluation of each learner 10 times, varying the random seed. Again, we use Adam optimizer and a learning rate of $10^{-3}$. Due to the large number of test examples and low performance of the learners, all FPA scores would be equal to zero. Hence, we follow~\cite{Lake2017} and use per-sequence accuracy, i.e.\ the ratio of the sequences with all output tokens predicted correctly.

\paragraph{Results}
We report our results in Table~\ref{tab:scan}. First, we see that CNN-s2s learners have a strong preference to \texttt{comp}, both in accuracy and description length. Furthermore, we observe that with an increase in the kernel size, description length of \texttt{mem} increases, while description length of \texttt{comp} decreases, indicating that the preference for \texttt{comp} over \texttt{mem} grows with the kernel width.  We believe this echoes findings of~\citep{Dessi2019}.

While accuracy is well below $0.01$ for all other learners/candidate combinations (and rounded to 0.00), according to the description length, Transformer and LSTM-based learners \textit{also} have preference for \texttt{comp} over \texttt{mem}. This can be due to the transfer from compositional training examples, that can make \texttt{comp} explanation most ``simple'' given the dataset. Hence, the failure for systematic generalization in SCAN comes not from learners' preferences for \texttt{mem}. We believe this resonates with the initial qualitative analysis in~\citep{Lake2017}.

\begin{table}[tb]
\centering
\resizebox{0.6\textwidth}{!}{
\begin{tabular}{lcccccccc|cc}
\toprule
 & \multicolumn{2}{c}{Accuracy} &\multicolumn{2}{c}{$L$, $\times 1000$ nats} \\
 & \texttt{comp} & \texttt{mem} & \texttt{comp} & \texttt{mem} \\
 \midrule
LSTM-s2s no att. & $0.00$ & $0.00$ & $\textbf{8.3}^*$ & $45.0$ \\
LSTM-s2s att. &  $0.00$ & $0.00$ & $\textbf{9.1}^*$ & $34.8$\\

CNN-s2s, kernel width 3 & $0.14$ & $0.03$ & $\textbf{3.5}^*$ & $19.0$ \\
CNN-s2s, kernel width 5 & $0.26$ & $0.02$ & $\textbf{2.0}^*$ & $21.8$ \\
CNN-s2s, kernel width 8 & $0.36$ & $0.01$ & $\textbf{1.8}^*$ & $24.3$ \\
Transformer & $0.00$ & $0.00$ & $\textbf{7.3}^*$ & $23.7$ \\
\bottomrule
\end{tabular}
}
\caption{SCAN: Accuracy is averaged across seeds and examples. Description length $L$ is averaged across examples and seeds. The lowest $L$ are in bold and $*$ denotes stat.\ sig.\ difference in  $L$ ($p < 10^{-3}$, paired t-test).}
\label{tab:scan}
\end{table}

\section{Studying inductive biases of LM-like architectures}

While in this paper we focused on studying inductive biases of seq2seq architectures, we believe our entire framework can be used for investigating biases of architectures used in language modeling (LM). As language modeling emerges as a general few-shot learning mechanism where textual prompting is used as an interface~\citep{Brown:etal:2020}, it becomes important to understand how models generalize in such a setup. In this Section, we demonstrate the applicability of our tasks and measures to such learners and scenarios.

We propose to study inductive biases of LM-like architectures by using prompt-based versions of our tasks akin to GPT2~\citep{Radford:etal:2019} \& GPT3~\citep{Brown:etal:2020}. As an example, we can train an LM-like architecture to continue the sequence ``<sos>aaa<sep>'' as "<sos>aaa<sep>bbb<eos>" and then prompt it with "<sos>aaaa<sep>" and check the output: is it "<sos>aaaa<sep>bbb<eos>" (\texttt{mem}) or "<sos>aaaa<sep>bbbb<eos> (\texttt{count})? Such formulation makes it trivial to adapt our tasks (Section~3) for the architectures used in language modeling. However, training differs from that of a language model due to the presence of the prompt.

In the following, we experiment with a variant of Transformer, namely joint source-target self-attention learner introduced by \cite{He:etal:2018}. We use the code provided in \citep{Fonollosa:etal:2019}.\footnote{Code link: \url{https://github.com/jarfo/joint}. However,  unlike \cite{Fonollosa:etal:2019}, we do not consider the locality constraint, and set the kernel\_size\_list parameter to None. This makes the architecture equivalent to the one introduced in~\citep{He:etal:2018}.} The joint source-target self-attention learner differs from the structure of Transformer in three ways. First, instead of attending  to  the last layer of the encoder in standard Transformers, here, each layer
in the decoder attends to the corresponding layer in the encoder. Second, the separate encoder-decoder attention module and the decoder self-attention are merged into one attention, called mixed attention. The mixed attention is hence used to extract information both from the source sentence and the previous target tokens. Finally, joint source-target self-attention shares the parameters of attention and feed-forward layer between the encoder and decoder.

The use of mixed attention and the sharing of parameters make the encoder/decoder distinction artificial. Indeed, we can see this learner as a "decoder-only" LM-like architecture that is adapted to performing seq2seq tasks in a way we described in the previous paragraph.

We use
the same  hyper-parameters of Transformer presented in the main text. Preliminary experiments showed that joint source-target self-attention learners do not  succeed in the \textit{Hierarchical-or-Linear} and  \textit{Composition-or-Memorization} tasks (i.e., less than $70\%$ of the seeds learned the \emph{training} set) when embedding size $S_{emb}=16$ (the one used in the main experiments). We hence set $S_{emb}=64$. The remaining hyper-parameters remain unchanged. Note that, according to Table~\ref{tab:embed}, there is no switch of biases for any setting when considering $S_{emb}=64$ compared  to $S_{emb}=16$. Specifically for Transformer, the only difference is that with $S_{emb}=64$, the latter shows even a stronger bias towards the hierarchical rule in the \textit{Hierarchical-or-Linear} task.

Finally, similar to Sections~\ref{sec:hyperparam_archi} and \ref{sec:hyperparam_training}, we only consider the \textit{Count-or-Memorization} task with $l= 40$, the \textit{Add-or-Multiply} task with $l= 20$, the \textit{Hierarchical-or-Linear} task with $d= 4$ and the \textit{Composition-or-Memorization} task with $M= 36$ and run $20$ seeds per setting. Results are reported in Table~\ref{tab:selfatt}.

First, when considering  the arithmetic tasks (i.e., \textit{Count-or-Memorization} and \textit{Add-or-Multiplication}), we note a clear preference for the memorization rule (with a zero $L$ and $1.00$ FPA) similar to Transformer behavior (see Table~\ref{tab:embed}). Second, joint source-target self-attention learners are, similarly to Transformers, biased towards the \texttt{hierar} rule with 100\% of the seeds generalized perfectly to the \texttt{hierar} rule and a significantly lower $L$. Finally, for  the \textit{Compositional-or-Memorization}, while only 1 seed generalized perfectly to the \texttt{comp} rule, $L$ shows a significant  preference for  the \texttt{mem} rule, in agreement  with  Transformers' biases.

Overall, our experiments in this Section indicate that the inductive biases of the "decoder-only" Transformer learner are very close to that of a standard Transformer seq2seq learner. On a higher level, we have demonstrated that our tasks and the description length measure can be applied for studying inductive biases of architectures that are often used in language modeling, indicating a high universality of the approach.

\begin{table}[tb]
\centering
\resizebox{1\textwidth}{!}{
\begin{tabular}{lcccccccccccc}
\toprule
& \multicolumn{2}{c}{Count-or-Memorization}  &&  \multicolumn{3}{c}{Add-or-Multiplication}  &&  \multicolumn{2}{c}{Hierarchical-or-Linear} &&  \multicolumn{2}{c}{Composition-or-Memorization} \\
\cmidrule{2-3} \cmidrule{5-7} \cmidrule{9-10} \cmidrule{12-13}
& \texttt{count} & \texttt{mem} && \texttt{add} & \texttt{mul} & \texttt{mem} && \texttt{hierar} & \texttt{linear} && \texttt{comp} & \texttt{mem}\\
\midrule
 FPA  & 0.00 & 1.00 && 0.00 & 0.00 & 1.00 && 1.00 & 0.00 && 0.10 & 0.00 \\
 $L$, nats & 160.31 & \textbf{0.00$^{*}$} &&
 71.55 & 121.09 & \textbf{0.00$^{*}$} &&  \textbf{2.59$^{*}$} & 74.90 && 96.52 & \textbf{57.94$^{*}$}\\
 \bottomrule
\end{tabular}
}
  \caption{Measuring biases of joint source-target self-attention learners: FPA measures the fraction of seeds that generalize according to a particular rule. Description length $L$ is averaged across examples and seeds. The lowest $L$ are in bold and $*$ denotes stat. sig. difference in $L$ ($p <10^{-2}$, paired t-test).}
  \label{tab:selfatt}
\end{table}

\section{Evolution of inductive biases at training}
The description length measure that we defined by Eq.~\ref{eq:online} represents  both (a) how close the learner's generalization is to a fixed ``explanation'' of the data, and (b) if it can learn this explanation quickly, with few examples. In this Section, we aim to peak into the latter process, by looking how quick a learner can pick up a candidate explanation. To do that, we use the \textit{Compositional-or-Memorization} task with $1000$ different primitives.

We organize the experiment in the following way. We start by training learners on the training data, composed of all primitives and $M=10$ (i.e., $10$ compositional examples). We measure description length of the \texttt{comp} candidate generalization on the remaining (1000-10 compositional examples). Next, we train learners from scratch, but this time we add $10$ additional compositional example (M + 10), and measure the description length on the remaining 1000-20 compositional examples. We repeat this procedure until all compositional examples are exhausted. As in this process the description length will decrease due to simply having less examples left for the evaluation, we normalize it by dividing by the number of remaining examples. We denote the result as $\bar L$.

Since this is a new task with a larger number of primitives, the hyperparameters used in main experiments wouldn't allow the models to reliably learn the training set.  We hence use an embedding size of 64 for all architectures to have more robust convergence. For Transformer only, we also use a larger architecture with $2$ layers. All the other hyperparameters remain unchanged compared to the experiments in the main text and we run $20$ seeds for each setting. We report results in Figure~\ref{fig:DL_dynamic}.

Figure~\ref{fig:DL_dynamic} shows that CNN-s2s are the fastest to prefer the compositional rule, starting already with low $\bar L$. Indeed, when provided by only $20$ compositional examples, $\bar L$ is almost zero. On the other extreme, Transformers’ behavior persists irrespective of $M$ with a large variance. While we note a decrease of $\bar L$ when increasing $M$, this tendency is very weak. Interestingly, while LSTM-s2s no att.~learners start as less biased towards compositionality compared to Transformers, they display a lower $\bar L$ after seeing $120$ compositional examples, and converge to an almost zero $\bar L$ with $M>600$.

\begin{figure}
  \centering
      \includegraphics[width=0.7\textwidth]{Figure/largeDL_epoch_cum.pdf}
  \caption{Per-example average description length $\bar L$ (nats), across $20$ seeds for each learner as a function of number of compositional training examples. Shaded area represents 90\% confidence interval.}\label{fig:DL_dynamic}
\end{figure}

config: arxiv


TITLE: Hamilton or Hamilton-Jacobi formalism with Hamiltonian equal to zero
QUESTION [3 upvotes]: I have the Lagrange function:
$$L=\sqrt{\frac{\dot{x}^2+\dot{y}^2}{-y}}.\tag{1}$$
The energy is then:
$$H=\dot{x}\frac{\partial L}{\partial \dot{x}}+\dot{y}\frac{\partial L}{\partial \dot{y}}-L=0.\tag{2}$$
Can I somehow apply in this case the Hamilton or Hamilton-Jacobi formalism to find the motion?

REPLY [1 votes]: OP's Lagrangian (1) is the square root Lagrangian for a massive relativistic point particle (or equivalently, geodesics) in a curved space with metric
$${\bf g}~=~\frac{\mathrm{d}x\odot \mathrm{d}x+ \mathrm{d}y\odot \mathrm{d}y}{-y}, \qquad y~<~0 .\tag{1}$$
The square root Lagrangian (1) has worldline reparametrization invariance, i.e. gauge symmetry. As a result, the Lagrangian energy function $h(x,y,\dot{x},\dot{y})$ [and the Hamiltonian $H(x,y,p_x,p_y)$ in the corresponding Hamiltonian formalism, cf. e.g. this Phys.SE post] vanish.
The easiest way to proceed is to consider the corresponding non-square root Lagrangian, cf. e.g. this Phys.SE post. Then the Legendre transformation, Hamiltonian & Hamilton-Jacobi theory are in principle straightforward to set up.


TITLE: Infinite Cardinal number power.
QUESTION [0 upvotes]: Let $a$ and $b$  are two infinite cardinal number than can i say that $a^{b}=2^{b}$?
I am thinking so because of there this true for $\aleph_{0}$ and $c=2^{\aleph_{0}}$ as $\aleph_{0}^{c}=2^{c}$ and $c^{\aleph_{0}}=2^{\aleph_{0}}.$

REPLY [2 votes]: No. Take $a=2^{2^{\aleph_0}}$ and $b=\aleph_0$, then $$a^b=(2^{2^{\aleph_0}})^{\aleph_0}=2^{2^{\aleph_0}\cdot\aleph_0}=2^{2^{\aleph_0}}>2^{\aleph_0}.$$