6
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Commented Dec 28, 2011 at 14:18
  • $\begingroup$ 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? $\endgroup$
    – joro
    Commented Dec 28, 2011 at 14:39
  • 2
    $\begingroup$ @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". $\endgroup$ Commented Dec 28, 2011 at 16:49
  • $\begingroup$ 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 iag.uni-hannover.de/~schuett/publik_en.html $\endgroup$ Commented Dec 28, 2011 at 17:34
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Dec 31, 2011 at 5:07

1 Answer 1

8
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ "Hence... and multiplying each coefficient..." do you mean "multiplying the $n \equiv 2 mod 3$ coefficients"? $\endgroup$ Commented Dec 29, 2011 at 4:08
  • $\begingroup$ @David Hansen: Yes, thanks; fixed now. $\endgroup$ Commented Dec 29, 2011 at 4:35
  • $\begingroup$ 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$). $\endgroup$ Commented Dec 31, 2011 at 19:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .