MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

BACKGROUND: The question, which has its roots in a question asked on MO by O'Bryant, concerns the relative density of certain subsets, $B$, of ${\mathbb N}$ in congruence classes modulo a power of 2. Let $I$ be such a congruence class. I'll say that $B$ is "stable in $I$" if there is a $c$ such that $B$ has relative density $c$ in $J$ whenever $J$ is a congruence class contained in $I$ whose modulus is also a power of 2.

Suppose $B$ consists of all $n$ such that the coefficient of $x^n$ in the reciprocal of the element $g=1+x+x^4+x^9+x^{16}+\dots$ of ${\mathbb Z}/2[[x]]$ is 1. Cooper et al. showed that $B$ has density 0 in 12 of the mod 16 congruence classes. I extended the result to 3 of the 4 remaining classes. But calculations by O'Bryant suggest that in the class 15 mod 16, $B$ is stable with relative density $1/2$. For a detailed account see my note Disquisitiones Arithmeticae and online sequence A108345.

These QUESTIONS pertain to sets introduced by Cooper et. al:

  1. Replace the exponents $0, 1, 4, 9, \dots$ in $g$ by the numbers $3n^2-2n$, $n \in {\mathbb Z}$, to get a new $B$. This $B$ has density 0 in 7 of the classes mod 8. Does the computer suggest that it is stable with relative density 1/2 in the class 0 mod 8?

  2. Suppose the exponents are $5n^2-4n$, $n \in {\mathbb Z}$. Does the computer suggest that there's a $q$ such that the new $B$ you get is stable in each mod $q$ congruence class? And if so, what do the relative densities appear to be? (The density is provably 0 in some mod 8 classes).

  3. Answer the same question as 2. when the exponents are the $5n^2-2n$, $n \in {\mathbb Z}$.

EDIT: I'll give a modified and generalized version of the question (and an expansion of my answer) using notation and ideas from my MO question on characteristic 2 thetas. Let $L$ be the field of formal Laurent series in $x$ over ${\bf Z}/2$. If $f$ (not zero) is in $L$, $B(f)$ consists of all $n$ for which the coefficient of $x^n$ in $1/f$ is 1. Now fix $l=2m+1$, $m>0$, and for $i$ in $\lbrace1,...,m\rbrace$ let $[i]$ be the element of ${\bf Z}/2[[x]]$ defined in the "thetas" question.

Question: For $q$ a power of 2, what does the computer suggest about the relative density of $B([i])$ in the various mod $q$ congruence classes? (Since all elements of $B[i]$ are congruent to $-(i^2)$ mod $l$, these relative densities are at most $1/l$).

Example: When $l=3$, it can be shown that $B([i])$ has density 0 in all congruence classes mod 8, with the possible exception of 7. And the computer (perhaps) indicates that in the 7 mod 8 class (or any class contained therein) the relative density is 1/6.

My "answer" generalizes the first sentence of the example. I made no computer calculations--indeed the computer evidence is at first sight contrary to my results because of the slow approach to zero. Let $L(q)$ contained in $L$ be the field of formal Laurent series in $x^q$. Then $L$ is the direct sum of the $(x^k)L(q)$, $k$ in $\lbrace0,...,q-1\rbrace$. Let $p_{(q,k)}$ be the obvious projection map $L\to(x^k)L(q)$. Let $S$ contained in

${\bf Z}/2[[x]]$

be the smallest ring that contains all the $[i]$ and is stable under the $p_{(q,k)}$ for all $q$ and $k$. It can be shown that every element of $S$ is the mod 2 reduction of the Fourier series of an integral weight modular form for a congruence group. A theorem of Serre then shows that if $\sum((c_n)(x^n))$ is in $S$ then the set of $n$ for which $c_n$ is 1 has density 0.

As a corollary one finds: Let $p$ be a $p_{(q,k)}$. If $p(1/[i])$ is in $S$ then $B([i])$ has density 0 in the class $k$ mod $q$.

By making use of the quintic relations from my theta question I can show that the hypothesis of the theorem holds in various cases. In particular suppose $i$ is prime to l. When $l=5$, $B=B([i])$ has density 0 in each mod 32 class except perhaps the 5 classes $n=7$ mod 8 and $n=28$ mod 32. When $l=7$, $B$ has density 0 in each mod 32 class except perhaps the 7 classes 7 mod 8, 14 mod 16 and 28 mod 32. When $l=9$, $B$ has density 0 in each mod 64 class except perhaps the 19 classes 1 and 7 mod 8, 28 mod 32, and 48 mod 64.

In the various classes qualified by "except perhaps" in the above paragraph (and the subclasses contained therein) it seems plausible that the relative densities are $1/(2l)$. But this may be wishful thinking. I hope that someone will make further calculations.

FURTHER EDIT: Heres a more explicit and more speculative version of my question. Let n_j be the negative exponents appearing in the Laurent series 1/[i], 1/[2i], 1/[4i], i/[8i],..., and q_j be the largest power of 2 dividing n_j.

QUESTION: Does computer evidence support the following speculations?

(1) The relative density of B([i]) in each congruence class n_j mod 8q_j, and in all congruence classes modulo a power of 2 contained therein, is 1/(2l).

(2) Outside of these congruence classes B([i]) has density 0.

For example when l=9 and i=1 the n_j are -16,-7,-4 and -1, and the classes in (1) are 1 mod 8, -1 mod 8, -4 mod 32 and -16 mod 128. The technique I indicated in my earlier edit shows that (2) holds in this case, so one gets 128-37 classes mod 128 where B has density 0. The technique also shows that (2) holds when l=3,5 or 7. This isn't much evidence, and there's far less for (1). But as these are the simplest answers one might hope for, I'd be interested in any calculations concerning them.

share|cite|improve this question
Hi Paul, you forgot to put brackets around the exponent $16$ in your equation g=1+x+x^4+x^9+x^16..., you should have used g=1+x+x^4+x^9+x^{16} to get the correct result $g=1+x+x^4+x^9+x^{16}...$ I don't have enough points to edit that for you, so you'll have to fix that. And you should just be able to hit the "edit" button under your question to perform the edit. MO shouldn't lose the question if you do that. – sleepless in beantown Nov 18 '10 at 4:25
I've attempted to TeX the most recent edit. Hope I didn't corrupt the meaning. – Gerry Myerson Nov 18 '10 at 5:23
Gerry-Thanks for the TeXing; I don't know how to do such things. The meaning is intact, though I prefer Z/2 to the ambiguous Z_2 – paul Monsky Nov 19 '10 at 2:39
@paul, ${\bf Z}_2$ replaced by ${\bf Z}/2$. – Gerry Myerson Nov 19 '10 at 11:31

This is really commentary on 2. and 3. of my question in the light of recent discoveries, but as I don't know how to edit the question without losing it, I'll post my discoveries as an answer. Following Cooper et. al. denote the sets B of 2. and 3. by B_(1,10) and B_(3,10). I can now prove:

a. The n in B_(1,10) that are neither 7 mod 8 nor 0 mod 32 have density 0.

b. The n in B_(3,10) that are neither 0 mod 8 nor 25 mod 32 have density 0.

I suspect that B_(1,10) is stable with relative density 1/2 in each of the 5 remaining congruence classes mod 32, and that the same is true for B_(3,10). It would in fact suffice to handle the classes 7 mod 8 for B_(1,10) and 0 mod 8 for B_(3,10), and I would appreciate calculations for these mod 8 congruence classes to confirm or disconfirm my suspicions.

The proofs of a. and b. use a deep result of Serre's on the mod J reduction of the Fourier expansion of a modular form of integral weight,when the Fourier coefficients lie in a number field, together with some simple techniques from my answers to O'Bryant's questions. I hope to post the proofs on arXiv one of these days.

EDIT: The arguments can now be found on arXiv NT 1107.4137, "The reciprocals of some characteristic 2 'theta series' ". I use the techniques mentioned above to prove the analogues to (a) and (b) when l=7,9,11,13 and 15 as well. (See the edit to my question to see what I'm describing). But I can't handle one class mod (128) for l=13 and 15, and though my method might give density 0 results in some congruence classes when l>15, the computer isn't up to the job. So I'd still be grateful to anyone willing to make further computer calculations to see whether my speculations are plausible.

share|cite|improve this answer

For prime l I've now proved (a corrected version of) the speculation (2) made in the further edit to my question. (See Theorem I below). The proof avoids the extensive computer verifications made in arXiv NT 1107.4137. So let K be an algebraic closure of Z/2. Call an element g=a_0+a_1(x)+a_2(x^2)+... of K[[x]] "sparse" if the n with a_n non-zero form a set of density 0.

Lemma 1----Suppose g is in the subring R of K[[x]] generated by K and the [i]. Then g is sparse. (This follows from the fact that the elements of R are the mod 2 reductions of Fourier expansions of modular forms of integral weight, and the theorem of Serre mentioned in my previous answer).

We have shown in another question that the above ring R is the co-ordinate ring of an affine curve C. Let m_0 be the maximal ideal of R generated by [1],...,[l-1], and p_0 be the point of C corresponding to m_0. We showed in addition (using the fact that l is prime) that m_0 is the only maximal ideal of R containing any of [1],...,[l-1], and that there are (l-1)_/2 linear branches at p_0 with distinct branch tangents.

Lemma 2---Suppose g=a_0+a_1(x)+... is in K[[x]], that g is the quotient of an element of R by a product of powers of [i], and that g has positive ord at every branch of C centered at p_0. Then g is sparse. (For g is in the localization of R at every maximal ideal other than m_0. Furthermore if n is large g^n is in the localization of R at m_0. So for n large, g^n is in R, and is sparse by Lemma 1. Take n to be a large power of 2 to get the result.

---------Now let U=U_2 be the operator K[[x]]-->K[[x]] taking sum(a_n)(x^n) to sum(a_2n)(x^n). Note that U([i][i]g)=[i]U(g).

Lemma 3---The subring of Z/2[[x]] generated by the [i] is stable under U. (It suffices to show that U takes a product of terms, [ ], to an element of this ring. We argue by induction on the number of terms in the product. We may assume that the first 2 terms are [2i] and [2j]. Then [2i][2j] is the sum of [2i][j]^4, [2j][i]^4 and ([i+j][i-j])^2. Multiplying by the remaining terms in the product, applying U, and using induction we get the result).

Now let L be the field of Laurent series in x over Z/2, and L(q) be the field of Laurent series in x^q, where q is a power of 2. We write p_(q,k) for the obvious projection map L-->(x^k)L(q). Note that for g in Z/2[[x]], U(g) is the square root of p_(2,0)(g). So if g is in the ring of Lemma 3, then p_(q,0)(g) is a qth power in that ring.

Theorem I---Let q be a power of 2, and suppose that k is in {0,1,2,3,4,5,6,7}. Suppose that g_i=p_(8q,kq)(1/[i]) is in Z/2[[x]] for all i--that is to say that no negative exponents appear in any g_i. Then each g_i is sparse. (In other words each B([i]) has density 0 in each congruence class kq mod 8q).

To prove this note that p_(q,0)(1/[i]) is the quotient of p_(q,0)([i]^(8q-1)) by [i]^8q. The paragraph before Theorem I shows that this is the quotient of v^q by [i]^8q for some v in R. Applying p_(8q,kq) we find that g_i=(1/[i]^8q)(w^q), where w=p_(8,k)(v). Since p_(8,k) stabilizes R, g_i is the quotient of an element of R by a power of [i]. The exponent restriction tells us that if g is a g_j, then g has positive ord at each branch of C centered at m_0, and we invoke Lemma 2.

Example: Suppose l=13, q=16 and k=3. The negative exponents appearing in the i/[i] are -36,-23,-10, -25, -16,-9,-4,and -1. Since none of these is congruent to 48 mod 128, all the g_i are in Z/2[[x]]. It follows from Theorem I that each B([i]) has density 0 in the congruence class 48 mod 128, a result that had eluded me.

share|cite|improve this answer

Your Answer


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.