Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$.

Question. 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$? Kevin O'Bryant has verified that this holds when $n$ is 512 or less.

Remark. 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 this and this 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$.

(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$).

share|improve this question
    
Wadim, You miscalculated--the quotient is 1+x^3-2*x^4+2*x^5-x^6+.... Of course over Z/2 the quotient is 1+x^3+x^6... Paul –  paul Monsky Jul 4 '10 at 12:39
    
I now think I can answer my own question (in the affirmative) with a rather simple argument. But I'll leave things as they are for the time being for the interest of viewers. –  paul Monsky Jul 4 '10 at 13:07
    
Hi, Folks. I can certainly believe the Question, for the quotient I get, by hand, exponents 0, 3, 6, 9, 10, 11, 13, 15, 17, 19, 23, 28, 33, 36, 37, 41, 47, 49, 55, 57, 59, 65, 66, 71,... Maybe something will come to me, but meanwhile it appears Paul thought of a solution. Have you seen Greg Kuperberg's take on the original project? mathoverflow.net/questions/26839/… –  Will Jagy Jul 5 '10 at 0:27
    
The differential operator $D=\operatorname{id}+x(d/dx)$ "kills" the unwanted odd powers, so that the original problem is equivalent to $D(fg)\equiv D(f)g^2\equiv D(f)g(x^2)\pmod{2}$ where the congruence is applied to all coefficients in the power series expansions. I wonder whether this is helpful, but $f$ and $g$ are related to the thetanulls, $2f=x^{-1/4}\vartheta_2(x)$ and $2g=1+\vartheta_3(x)$ where $x=\exp(\pi i\tau)$, and there exist DEs for the latter ones. –  Wadim Zudilin Jul 5 '10 at 2:00
2  
Paul, as one of the interested viewers I would be glad to learn about your simple argument. (Your comment is like Fermat's "I have discovered a truly marvelous proof that...") Thanks! –  Wadim Zudilin Jul 5 '10 at 12:43

3 Answers 3

The coming below is nothing else but thinking loudly.

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(*) $$

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}}. $$

In addition, we can use repeatedly $$ h(x^2)\equiv h(x)^2\pmod{2}. $$

Edit. 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$.

share|improve this answer
1  
Why do you always post almost-complete solutions and leave completing them to me? Your (**) easily reduces to $g+x\frac{d}{dx}g\equiv g^4\mod 2$ (the reduction only uses basic properties of working in characteristic $2$, such as $g^8-g^{16}\equiv \left(g-g^2\right)^8\mod 2$, and it uses the fact that $\frac{d}{dx}\left(FG\right)\equiv F\frac{d}{dx}G\mod 2$ if $\frac{d}{dx}F\equiv 0\mod 2$, which for instance is satisfied if $F$ is a square of something). Now this is equivalent to saying that the positive integers which have an odd number of different representations as sums of four squares ... –  darij grinberg Jul 5 '10 at 11:17
1  
... (the order matters here) are the even squares. This is clear, because the even squares are exactly those positive integers which have a representation as sums of four EQUAL squares, and all the other representations can be easily grouped into pairs (first we group all the $a^2+b^2+c^2+d^2$ representations with $a\neq b$ into pairs in an obvious way; then, all the $a^2+b^2+c^2+d^2$ representations with $a=b$ and $c\neq d$; then, at last, those with $a=b\neq c=d$). –  darij grinberg Jul 5 '10 at 11:20
    
Darji, why are you surprised? If you lokk at the list of my publications, you'll see that I normally don't work alone. :-) In fact, I was thinking of the problem during several breaks, and at some point lost interest to it. (Paul mentions he already know the solution, not very encouraging.) –  Wadim Zudilin Jul 5 '10 at 11:30
    
Wadim: I don't think your passage from * to ** is correct, since * expresses a tricky fact about representations by binary quadratic forms, while ** is a triviality (since the exponents occurring in g-g^4, viewed as a power series over Z/2 are all odd). –  paul Monsky Jul 5 '10 at 12:36
    
Paul, the problem really exhausted me (especially, in view of the existence of a simpler argument from your side). The passage took several pages, therefore at the end I am not very confident in its truth. I also tried to use the relations with the thetanulls, but everything was messy again. (I am not a special lover of complicated solutions.) –  Wadim Zudilin Jul 5 '10 at 12:49
up vote 1 down vote accepted

(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).

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.

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$.

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.

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

share|improve this answer

Part 2--the curious fact

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.

If 2 or more a(p) are odd, 4 divides I and J

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).

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.

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_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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.