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

I am not familiar with newforms, so this may not make any sense.

OEIS sequence A116418 is Expansion of a newform level 18 weight 3 and character [3]

Numerical evidence suggest that up to $10^5$ $$ \text{A116418}[n] \equiv \sigma(3n+1) \pmod 3$$

What is the complexity of computing A116418[n], possibly assuming $n$ is factored (for modular form coefficients after $n$ is factored the coefficient is efficiently computable).

Gjergji Zaimi proved a similar congruence involving eta and A116418 is expansion of an eta formula.

Added My main interest is computing $\sigma(3n+1) \mod 3$ and a comment by Dror Speiser suggests the coefficient of the newform is computable in polynomial time assuming $n$ is factored.

The factorization of $n$ is not related related to the factorization of $3n+1$ and for numbers of form $3 \cdot 2^n + 1$ the factorization is trivial.

Is A116418 really the expansion of the newform or is it a typo in OEIS?

Is the congruence $ \text{A116418}[n] \equiv \sigma(3n+1) \pmod 3$ identity or just coincidence for the the first $10^5$ terms?

share|cite|improve this question
Computing the nth coefficient, assuming n is factored, is polynomial in the level, weight, and $\log{n}$. This is proven (for level one, but claimed to work for all levels) in Computational Aspects of Modular Forms and Galois Representations, Edixhoven et al. – Dror Speiser Dec 28 '11 at 14:18
Thank you Dror. I am interested in computing sigma(3n+1) mod 3. The factorization of $n$ is not related to the factorization of $3n+1$ so one can factor $n$ by say ECM and for numbers of form say $3 \cdot 2^n + 1$ the factorization is trivial. Is indeed A116418 the expansion of the newform in question or it is a typo in OEIS? – joro Dec 28 '11 at 14:39
@joro: The sequence's nth number is the $3n+1$-th coefficient of the modular form - so $\sigma(3n+1)=a_{3n+1}(f)$, and not $\sigma(3n+1)=a_n(f)$. So you would still need to factorise $3n+1$. In any case, your observation is not a coincidence. Indeed, the modular form is equal mod 3 to an Eisenstein series. You can read up on this by searching keywords such as "congruences between modular forms". – Dror Speiser Dec 28 '11 at 16:49
It seems this newform has CM by $K=\mathbf{Q}(\sqrt{-3})$, in which case it comes from a Grössencharakter $\psi$ of $K$ (by a theorem of Ribet). Its Fourier expansion then has the form $f=\sum_{I} \psi(I) q^{N(I)}$ where sum is taken over ideals (I don't know if this helps for computation). About CM newforms a good reference is Matthias Schütt's dissertation – François Brunault Dec 28 '11 at 17:34
If this form were CM then it would indeed help computation: the Edixhoven program would not be needed, and computing the $q^n$ coefficient would be almost(?) equivalent to factoring $n$. But alas it's not CM, see my answer below. – Noam D. Elkies Dec 31 '11 at 5:07
up vote 6 down vote accepted

[More a comment than an answer, but too long for the comment space]

Call this form $$ \varphi := \frac{\eta(q^3)^2 \eta(q^6)^3 \eta(q^9)^2}{\eta(q^{18})} = q - 2q^4 - 4q^7 + 6q^{10} + 8q^{13} \cdots. $$ The listing of coefficients in the OEIS is correct as far as it goes (checked with copy-and-paste to gp). The form is not CM: the coefficients are supported on $q^n$ with $n \equiv 1 \bmod 3$ but do not vanish even for $n$ such as $10$ and $22$ that are $1 \bmod 3$ but not norms from ${\bf Q}(\sqrt{-3})$. In particular the coefficients aren't multiplicative, so $\varphi$ isn't quite an eigenform. It seems that the relevant eigenforms are obtained as follows. Apply $w_{18}$ to get (within a multiplicative factor) $$ \phi := \frac{\eta(q^6)^2 \eta(q^3)^3 \eta(q^2)^2}{\eta(q)} = q + q^2 - 2q^4 - 3q^5 - 4q^7 - 2q^8 + 6q^{10} + 12q^{11} + 8q^{13} - 4q^{14} \cdots, $$ whose $q^n$ coefficient is 0 if $n \equiv 0 \bmod 3$, and coincides with the $q^n$ coefficient of $\varphi$ also when $n \equiv 1 \bmod 3$, but need not vanish for $n \equiv 2 \bmod 3$. Then "experimentally" if $m,n$ are relatively prime then the $q^{mn}$ coefficient of $\phi$ equals the product of the $q^m$ and $q^n$ coefficients, unless both $m$ and $n$ are $2 \bmod 3$, when the $q^{mn}$ coefficient is $-2$ times that product. Hence we obtain an eigenform by choosing a square root of $-2$ and multiplying the $q^n$ coefficient of $\phi$ by that square root for each $n \equiv 2 \bmod 3$.

As Dror Speiser notes, the Edixhoven program promises to compute the $q^n$ coefficient of such a form in time $\log^{O(1)}n$ for $n$ prime, and thus for all $n$ given the factorization of $n$; but I don't think this has been implemented yet to the point that one could actually carry out the computation this way. For specific forms there can be shortcuts that make a $\log^{O(1)}n$ computation practical (still assuming $n$ is factored), but here I've tried a few things and not yet(?) found such a shortcut.

[added later] Curiously the images of $\phi$ under the other two $w$ operators are in the linear span of $\varphi$ and $\phi$: if we write $$ \psi = \frac{\eta(q^3)^3 \eta(q^6)^2 \eta(q^{18})^2}{\eta(q^9)} = q^2 - 3q^5 - 2q^8 + 12q^{11} - 4q^{14} \cdots $$ for (a multiple of) the $w_2$ image, then $\phi = \varphi + \psi$, while $\varphi - 2 \psi$ is the multiple $$ \frac{\eta(q)^2 \eta(q^3)^2 \eta(q^6)^3}{\eta(q^2)} = q - 2q^2 - 2q^4 + 6q^5 - 4q^7 + 4q^8 + 6q^{10} - 24q^{11} + 8q^{13} + 8q^{14} \ldots $$ of the $w_9$ image.

share|cite|improve this answer
"Hence... and multiplying each coefficient..." do you mean "multiplying the $n \equiv 2 mod 3$ coefficients"? – David Hansen Dec 29 '11 at 4:08
@David Hansen: Yes, thanks; fixed now. – Noam D. Elkies Dec 29 '11 at 4:35
Using Magma I found out that $\varphi= \frac12 (f+\overline{f})$ where $f$ is a weight 3 newform of level 18 and coefficients in $\mathbf{Z}(\sqrt{-2})$. The character $\varepsilon$ of $f$ is the nontrivial character of conductor $3$. This is consistent with what you found because $\overline{f} = f \otimes \overline{\varepsilon}$ so that if we write $f = \sum a_n q^n$, we have $\varphi = \frac12 \sum a_n (1+\varepsilon(n)) q^n$ (this also explains the vanishing of the $n \equiv 2 \mod{3}$ coefficients of $\varphi$). – François Brunault Dec 31 '11 at 19:47

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.