Variations on a theme of O'Bryant, Cooper and Eichhorn concerning power series over $\mathbb Z/2\mathbb Z$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T02:30:01Z http://mathoverflow.net/feeds/question/30501 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/30501/variations-on-a-theme-of-obryant-cooper-and-eichhorn-concerning-power-series-ov Variations on a theme of O'Bryant, Cooper and Eichhorn concerning power series over $\mathbb Z/2\mathbb Z$ paul Monsky 2010-07-04T11:06:32Z 2011-12-27T03:53:16Z <p>Define 2 power series over the field $\mathbb Z/2\mathbb Z$ by $f=1+x+x^3+x^6+\dots$, the exponents being the triangular numbers, and $g=1+x+x^4+x^9+\dots$, the exponents being the squares. Write $f/g$ as $c_0+c_1x+c_2x^2+\dots$ with each $c_n$ in $\mathbb Z/2\mathbb Z$.</p> <p><strong>Question.</strong> Is it true that when $n$ is even then $c_n$ is 1 precisely when $n$ is in the set of even triangular numbers $\lbrace 0,6,10,28,36,\dots\rbrace$? <a href="http://mathoverflow.net/users/935/kevin-obryant" rel="nofollow">Kevin O'Bryant</a> has verified that this holds when $n$ is 512 or less.</p> <p><strong>Remark.</strong> If one writes $1/g$ as $b_0+b_1x+b_2x^2+\dots$, then $n\mapsto b_n$ is the characteristic function $\bmod 2$ of the set $B$ studied by O'Bryant, Cooper and Eichhorn (see <a href="http://mathoverflow.net/questions/26839/" rel="nofollow">this</a> and <a href="http://mathoverflow.net/questions/28462/" rel="nofollow">this</a> questions of O'Bryant on MO); they show that when $n$ is even then $b_n$ is 1 precisely when $n$ is twice a square. A positive answer to my question would give a nice characterization of those elements of $B$ that are congruent to $7 \bmod 16$.</p> <p>(I've used the modular forms tag because of the formal similarity of $f$ and $g$ to Jacobi theta functions, and the motivation of O'Bryant, Cooper and Eichhorn in looking at $B$).</p> http://mathoverflow.net/questions/30501/variations-on-a-theme-of-obryant-cooper-and-eichhorn-concerning-power-series-ov/30587#30587 Answer by Wadim Zudilin for Variations on a theme of O'Bryant, Cooper and Eichhorn concerning power series over $\mathbb Z/2\mathbb Z$ Wadim Zudilin 2010-07-05T06:22:09Z 2010-07-05T13:22:53Z <p>The coming below is nothing else but thinking loudly.</p> <p>The differential operator $$D=\operatorname{id}+x\frac d{dx}\colon h\mapsto (xh)'$$ "kills" the unwanted odd powers modulo 2. Indeed, if $$h=\sum_{n=0}^\infty a_nx^n=a_0+a_1x+a_2x^2+\dots,$$ then $$Dh=\sum_ {n=0}^\infty (n+1)a_nx^n \equiv\sum_ {k=0}^\infty a_ {2k}x^{2k}\pmod 2$$ where the congruence is applied to all coefficients in the power series expansions. Therefore, the OP asks for the congruence $$D\biggl(\frac fg\biggr)\overset?\equiv D(f)\pmod 2$$ to be true, which after multiplication by $g^2$ becomes (modulo 2) the congruence $$D(fg)\overset?\equiv D(f)g^2\equiv D(fg^2)\pmod{2},$$ equivalently, $$\frac{d}{dx}\bigl(xf(x)g(x)\bigr) \overset?\equiv\frac{d}{dx}\bigl(xf(x)g(x)^2\bigr)\pmod{2}.\qquad\qquad\qquad(*)$$</p> <p>The function $f(x)$ can be in a certain sense eliminated from the required formula by using $$g(x)=\sum_{n=0}^\infty x^{n^2} =\sum_{m=0}^\infty x^{(2m+1)^2} +\sum_{m=0}^\infty x^{(2m)^2} =xf(x^8)+g(x^4)$$ which implies $$f(x)=\frac{g(x^{1/8})-g(x^{1/2})}{x^{1/8}}.$$</p> <p>In addition, we can use repeatedly $$h(x^2)\equiv h(x)^2\pmod{2}.$$</p> <p><strong>Edit.</strong> Following the clear criticism from Paul, I will only indicate the obvious restatement of ($*$): $$\frac{d}{dx}\bigl(x^7(g(x)-g(x^4))g(x^8)(1-g(x^8))\bigr) \overset?\equiv0\pmod{16}.\qquad\qquad\qquad(**)$$ This new one does not look specially nice but involves a single series, $g(x)=1+x+x^4+x^9+\dots$.</p> http://mathoverflow.net/questions/30501/variations-on-a-theme-of-obryant-cooper-and-eichhorn-concerning-power-series-ov/30958#30958 Answer by paul Monsky for Variations on a theme of O'Bryant, Cooper and Eichhorn concerning power series over $\mathbb Z/2\mathbb Z$ paul Monsky 2010-07-07T21:20:01Z 2010-07-07T21:31:58Z <p>(Part 1)--My argument uses the following curious fact about ideals in $Z[i]$ and $Z[\sqrt{-2}].$ Suppose $n=8m+1$. Let $I=I(n)$ and $J=J(n)$ be the number of ideals of norm $n$ in $Z[i]$ and $Z[\sqrt{-2}]$. Then $I\equiv J$ (4) except when $m$ is odd triangular, in which case $I\equiv J+2$ (4).</p> <p>As a corollary we find that in $Z/2[[x]]$, $fg^2-fg$ is $x+x^3+x^{15}+x^{21}+\cdots$, the exponents being the odd triangular numbers. (I wonder if this is previously observed, and if it's related to congruence relations for modular forms). To prove the corollary it suffices to show: Let $I_1=I_1(m)$ be the number of solutions of $m=t+2s$ and $J_1=J_1(m)$ be the number of solutions of $m=t+s$ with $t$ triangular, $s$ a square. Then when $m$ is odd triangular, $I_1-J_1$ is odd; otherwise it is even. </p> <p>We compare $I_1(m)$ with $I(n)$. Suppose $m=t+2s$. Then $n=(8t+1)+16s$ and $8t+1=x^2$, $16s=y^2$ with $x$ odd and $x$, $y$ in $N$. $x+iy$ and $x-iy$ generate ideals of norm $n$ in $Z[i]$. These 2 ideals are distinct except when $m$ is triangular and $s=y=0$. Using the fact that $Z[i]$ is a PID we find that every ideal of norm $n$ comes from a decomposition $m=t+2s$, and that $I=2I_1$, except when $m$ is triangular in which case $I=2I_1-1$.</p> <p>Suppose $m=t+s$. Then $n=(8t+1)+8s$, and $8t+1=x^2$, $4s=y^2$ with $x$ odd and $x$, $y$ in $N$. $x+y\sqrt{-2}$ and $x-y\sqrt{-2}$ generate ideals of norm $n$ in $Z[\sqrt{-2}]$. As above, we find that $J=2J_1$, except when $m$ is triangular in which case $J$ is $2J_1-1$. Combining the result of this paragraph and the last with the curious fact we get the corollary.</p> <p>One now derives the answer to my question. Let $R=Z/2[[x^2]]$. As R-module, $A$ is the direct sum of $R$ and $xR.$ Let $pr$ be the $R$-linear map $A\to R$ which is id on $R$ and 0 on $xR$. Since $fg^2-fg=x+x^3+x^{15}+\cdots$, $pr(fg^2)=pr(fg)$. Since $pr$ is R linear and $1/g^2$ is in $R$. $pr(f)=pr(f/g)$. So for even $m$, the coefficient of $x^m$ in $f/g$ is the coefficient of $x^m$ in $f$, answering my question. (In his answer Wadim saw the projection argument but missed the implications)---To be continued</p> http://mathoverflow.net/questions/30501/variations-on-a-theme-of-obryant-cooper-and-eichhorn-concerning-power-series-ov/30964#30964 Answer by paul Monsky for Variations on a theme of O'Bryant, Cooper and Eichhorn concerning power series over $\mathbb Z/2\mathbb Z$ paul Monsky 2010-07-07T22:16:47Z 2010-07-07T22:16:47Z <p>Part 2--the curious fact</p> <p>The theory of quadratic fields tells us that I is the sum of the Jacobi symbols (-1/d) and J is the sum of the (-2/d) where d divides n. Write n as a product of powers of distinct primes, and let a(p) be the exponent to which p appears. Multiplicativity of the Jacobi symbol shows that I is a product of contributions, one from each p; the same holds for J. The contribution is even when a(p) is odd and vice versa. Several cases arise.</p> <p>If 2 or more a(p) are odd, 4 divides I and J</p> <p>Suppose a single a(p) is odd. Since n=8m+1, p=1 (8), (-1/p)=(-2/p)=1 and the contribution of p to each of I and J is 1+a(p). Since all other contributions are odd, I=J=0 (4) or I=J=2 (4) according as a(p) is 3 or 1 (4).</p> <p>Suppose n is a square so that m is triangular. Write n=s^2. Let p_i be the primes =5 (8) that divide s, and d_i be the exponents. Let q_i be the primes =3 (8) that divide s and e_i be the exponents.</p> <p>If m is even, n=1 (16), so s=1 or 7 (8), while if m is odd n=9 (16) and s= 3 or 5 (8). In the multiplicative group of Z/8, all the (-3)^d_i together with all the 3^e_i multiply to s or -s. It follows that the sum of all the d_i and all the e_i is even for even m and odd for odd m.</p> <p>p_i makes contributions of 1+2d_i and 1 to I and J, while q_i makes contributions of 1 and 1+2e_i. And every other prime makes the same (odd) contribution to I as it does to J. Also, mod 4, the product of the 1+2d_i is 1+twice the sum of the d_i, while the product of the 1+2e_i is 1+twice the sum of the e_i. Combining this with the result of the last paragraph we see that I=J mod 4 precisely when m is even. This concludes the proof of the curious fact.</p>