The beginning of the project is the following theorem due to Siegel, and Cohen and Zagier:
Theorem 2.1: Let $F_{k,D}$ be defined as follows: $$F_{k,D}(\tau) = -\frac{B_k}{4k} L(\chi_D, 1-k) + \sum_{n \geq 1} c_{k,D}(n)q^n$$
for $$ c_{k,D}(n) = \sum_{d|N} d^{k-1} \left( \frac{D}{d} \right) \sum_{|s|< (n/d)\sqrt(D), s \equiv (n/d)D \mod 2} \sigma_{k-1}\left( \frac{(n/d)^2 D - s^2}{4} \right) $$ then $F_{k,D} \in M_{2k}(\Gamma)$.
With the notation that $\sigma_{k-1}(\alpha) =0$ if $\alpha$ is not an integer, we can simplify the formula using $$S_k(m,N) = \sum_{s\in \mathbf Z} \sigma_{k-1}\left(\frac{m - s^2}{N}\right)$$
to the following: $$F_{k,D}(\tau) = -\frac{B_k}{4k} L(\chi_D, 1-k) + S_{k}(D,N) \cdot q + O(q^2)$$
For small values of $k$, we know that $M_{2k}(\Gamma) = \mathbb{C} \cdot E_{2k}$ for the Eisenstein series $$ E_{2k} = 1 + \frac{- 2 \cdot 2k }{B_{2k}} \sum_{n \geq 1} \sigma_{k-1}(n)q^n$$
For example, for $k=2$, $M_4(\Gamma)$ is generated by $$ E_4 = 1 + 240 q + O(q^2)$$ and so we have $F_{2,N}$ is a multiple of $E_4$, say $F_{2,N} = \alpha E_4$.
Comparing coefficients, $$a_0(F_{2,N}) = \frac{-1}{6 \cdot 8} L(\chi_D, -1) = \alpha $$
$$ a_1(F_{2,N}) = S_2(D,4) = \alpha \cdot 240$$
Comparing coefficients, we deduce that $$ L(\chi_D, -1) = \frac{- \cdot 6 \cdot 8}{240} \cdot S_2(D,4) = \frac{-1}{5} S_2(D,4) $$
def Sk(k,m,N):
o = sigma(ZZ(m).divide_knowing_divisible_by(N), k = k-1) if m%N == 0 else 0
cur = m-1
diff = 3
while cur > 0:
if (cur)%N ==0:
o += 2*sigma((cur).divide_knowing_divisible_by(N), k=k-1)
cur = cur - diff
diff = diff + 2
return o
@cached_function
def fund_discs(B,sqmod=1,cong=1,cl=0):
return [d for d in range(1, B, 1) if is_fundamental_discriminant(d) and Integers(sqmod)(d).is_square() and d % cong == cl]
In case the space $M_{2k}(\Gamma)$ has dimension larger than $1$, writing $F_{k,N}$ in an appropriate basis, we can get other formulas:
$$L(\chi_D, -3) = S_4(D,4)$$
$$L(\chi_D,-5) = -\frac{8S_6(D,4)}{65} -\frac{S_6(D,1) + 2^5 \left(\frac{D}{2}\right)S_6(D,4)}{195}$$
$$ = -\frac{2^3(3+2^2 \left(\frac{D}{2}\right))S_6(D,4) + S_6(D,1)}{195}$$
$$L(\chi_D,-7) = -\frac{24S_8(D,4)}{17} +\frac{S_8(D,1) + 2^{8-1} \left(\frac{D}{2}\right)S_8(D,4)}{153}$$ $$ = -\frac{2^3(3^3 +2^5\left(\frac{D}{2}\right))S_8(D,4) + S_8(D,1)}{153}$$
...
$$L(\chi_D,-11) = \frac{-9783S_{12}(D,4)}{13820} +3\frac{S_{12}(D,1) + 2^{12-1} \left(\frac{D}{2}\right)S_{12}(D,4)}{17275} + \frac{S_{12}(3^2D,4) + 3^{12-1} \left(\frac{D}{3}\right)S_{12}(D,4)}{276400}$$ $$ = \frac{(-20\cdot 9783 +3\cdot16\cdot2^{12-1} \left(\frac{D}{2}\right) + 3^{12-1} \left(\frac{D}{3}\right))S_{12}(D,4)+ S_{12}(3^2D,4)+ 3\cdot16S_{12}(D,1)}{276400}$$
There exists a more general version of Theorem 2.1 which works for general $k$.
Theorem 2.3: Let $D>1$ be a fundamental discriminant and let $k\geq 2$ be any integer. Let $\psi$ be a primitive character modulo $F$ with $\psi(-1) = (-1)^k$. Let $N$ be a squarefree integer such that $\gcd(F,ND) = 1$. Set $$c_{k,D}(0) = \frac{L(\psi,1-k)L(\phi\chi_D,1-k)}{4}\prod_{p\mid N} (1-\phi\chi_D(p)p^{k-1})$$ and for $n\geq 1$: $$c_{k,D}(n) = \sum_{d\mid n,\gcd(d,N)=1}\phi\chi_D(d)d^{k-1}\sum_{s\in\mathbf Z}\sigma_{k-1,\psi}\left(\frac{(n/d)^2D-s^2}{4N}\right)$$ where $\sigma_{k-1,\psi}(m) = 0$ if $m$ is not a positive integer and otherwise $\sigma_{k-1,\psi}(m) = \sum_{d\mid }\psi(d)d^{k-1}$. Then $$\sum_{n\geq 0}c_{k,D}(n)q^n\in M_{2k}(\Gamma_0(FN),\psi^2).$$
A consequence of this theorem is that there always exist relations as we found before between $L(\chi_D,1-k)$ and $S_k(mD)$ for appropriate $m$.
Corollary: Let $k\geq 2$ be even and $N\geq 1$ with $4\mid N$. Then there exists $t$ and constants $c_n$ for $1\leq n\leq t$ such that whenever $D$ is a square modulo $N$ we have
$$L(\chi_D,1-k) = \sum_{1\leq n\leq t}c_n S_k(n^2D,N)$$
So instead of finding relations theoretically we can search for them, knowing that they must exist.
N = 4*4
pts=[]
for D in fund_discs(3000, sqmod=N, cong=8, cl=1):
pts +=[(quadratic_L_function__exact(-1,D), Sk(2,D,N))]
points(pts)
Matrix(pts).right_kernel()
Vector space of degree 2 and dimension 1 over Rational Field Basis matrix: [1 2]
N = 4*12
pts=[]
for D in fund_discs(3000, sqmod=N, cong=3, cl=1):
pts +=[(quadratic_L_function__exact(-1,D), Sk(2,D,N))]
points(pts)
N = 4*12
pts=[]
for D in fund_discs(1000, sqmod=N, cong=3, cl=1):
pts +=[(quadratic_L_function__exact(-1,D), Sk(2,D,N),Sk(2,9*D,N))]
points(pts)
Our next goal is to find such relations for different $N$ and determine which relations are ''best'' to compute the special value $L(\chi_D,1-k)$ (i.e. find some cost function for these relations).
class QuadraticLValueRelation():
def __init__(self,N,Dcong,Dmod,k,dic):
self._k= k
self._N= N
self._Dcong = Dcong
self._Dmod= Dmod
self._dic= dic
pass
def __repr__(self):
return "Quadratic L-value relation given by sigma_%d(%d)L(chi_D,%d) = "%(self._k-1,self._N/4,1-self._k) + "+".join(r"%d/%d*S_%d(%d^2 D,%d)" %(v.numerator(),v.denominator(),self._k,ke,self._N) for ke,v in self._dic.iteritems()) + " for D = %d (mod %d)" % (self._Dmod,self._Dcong)
def _latex_(self):
return "\sigma_{%d}(%d)L(\chi_D,%d) = "%(self._k-1, self._N/4,1-self._k) + "+".join(r"%sS_%d\left(%d^2 D,%d\right)" %(latex(v),self._k,ke,self._N) for ke,v in self._dic.iteritems())+ " \\text{ when }D \equiv %d \pmod{%d}" % (self._Dmod,self._Dcong)
def cost(self):
N = ZZ(self._N)
Dcong= ZZ(self._Dcong)
Dmod = ZZ(self._Dmod)
mx = 0
gc = gcd(Dcong,N)
for D in Integers(N):
if Integers(Dcong)(D.lift()) != Dmod:
continue
new = sum([1 for n in Integers(N) if n^2 == D])
if new > mx:
mx = new
return max(self._dic.keys())*mx/N
def probapplies(self):
Dcong= ZZ(self._Dcong)
Dmod = ZZ(self._Dmod)
produ = 1
if Dcong % 2 == 0 and Dmod % 4 in [2,3]:
return 0
for (p,e) in factor(Dcong):
if p == 2:
mod16 =[1,5,9,13,8,12]
if e >=4:
if Dmod % 16 in mod16:
produ *= 1/(6*2^(e-4))
else: return 0
if e == 3:
if Dmod % 8 == 0 or Dmod % 8 ==4:
produ *= 1/6
else: produ *=1/3
if e == 2 or e ==1:
if Dmod % 4 ==0:
produ *= 1/3
else: produ *= 2/3
continue
if e >= 2 and Dmod % p^2 == 0:
return 0
if e == 1:
if Dmod % p == 0:
produ *= (p-1)/((p^2-1))
continue
produ *= p/(p^2-1)
else:
produ *= 1/(p^e - p^(e-2))
return produ
def test(self):
for D in fund_discs(1000, self._N, self._Dcong, self._Dmod):
if (sigma(self._N/4, k = self._k - 1)*quadratic_L_function__exact(1-self._k,D) != sum(v*Sk(self._k,ke^2*D,self._N) for ke,v in self._dic.iteritems())):
print quadratic_L_function__exact(1-self._k,D) , sum(v*Sk(self._k,ke^2*D,self._N) for ke,v in self._dic.iteritems()),self._dic
raise Exception
def find_relations(N, k=2, sample=10000, tmax=5, confidence=40):
fails = []
rell = []
divs = N.divisors()
for c in range(N):
found = False
discs = fund_discs(sample, sqmod=N, cong=N, cl=c)
if len(discs) >= confidence:
for t in range(len(divs)):
pts = [tuple([(sigma(N/4,k-1) if True else 1) * quadratic_L_function__exact(1-k,D)] + [Sk(k,d*d*D,N) for d in divs[:t]]) for D in discs[:confidence]]
#for t in range(tmax):
# pts = [tuple([sigma(N/4,k-1) * quadratic_L_function__exact(1-k,D)] + [Sk(k,n*n*D,N) for n in range(1,t+1)]) for D in discs[:confidence]]
if len(pts) >= confidence:
M = Matrix(pts)
R = M.right_kernel()
if R.dimension() == 1:
rel = R.basis()[0]
if (rel[0] != 0):
found = True
di = {n:-v for n,v in zip(divs[:t],rel[1:]) if n != 0 and v != 0}
ne = QuadraticLValueRelation(N,N,c,k,di)
#print rel,ne
rell += [ne]
break
if not found:
fails.append(c)
elif discs:
print "not enough discriminants: ",c
if fails:
print "failed: ",fails
return rell
We can now find relations for different $N$. For example for $N=12$:
relations = find_relations(12, 2, sample=6000, tmax=50, confidence=30)
for rel in sorted(relations, key=lambda rel: rel.cost()):
show(rel)
rel.test()
print " Cost of this relation: ", rel.cost()
print "Probability this relation applies to random D: ", rel.probapplies()
Cost of this relation: 1/6 Probability this relation applies to random D: 1/12
Cost of this relation: 1/6 Probability this relation applies to random D: 1/6
Cost of this relation: 1/3 Probability this relation applies to random D: 1/4
Cost of this relation: 1/3 Probability this relation applies to random D: 1/8
$N=28$:
The cost of computing $$S_k(m,N) = \sum_{s\in \mathbf Z} \sigma_{k-1}\left(\frac{m - s^2}{N}\right)$$
is
$$ \{ s \leq \sqrt{m} : s^2 \equiv D \text{ (mod } N )\} = \frac{\{ s \leq \sqrt{m} : s^2 \equiv m \text{ (mod } N )\}}{\{ s \leq \sqrt{m}\}} \sqrt{m}$$
approximated by
$$ \frac{\{ s \leq N : s^2 \equiv m \text{ (mod } N)\}}{\{ s \leq N \}} \sqrt{m} $$
relations = find_relations(28, 2, sample=6000, tmax=50, confidence=30)
for rel in sorted(relations, key=lambda rel: rel.cost()):
show(rel)
rel.test()
print " Cost of this relation: ", rel.cost()
print "Probability this relation applies to random D: ", rel.probapplies()
Cost of this relation: 1/7 Probability this relation applies to random D: 1/24
Cost of this relation: 2/7 Probability this relation applies to random D: 7/144
Cost of this relation: 2/7 Probability this relation applies to random D: 7/144
Cost of this relation: 2/7 Probability this relation applies to random D: 7/144
Cost of this relation: 1/2 Probability this relation applies to random D: 1/12
Cost of this relation: 1 Probability this relation applies to random D: 7/72
Cost of this relation: 1 Probability this relation applies to random D: 7/72
Cost of this relation: 1 Probability this relation applies to random D: 7/72
$N=124$:
relations = find_relations(124, 2, sample=10000, tmax=50, confidence=30)
for rel in sorted(relations, key=lambda rel: rel.cost()):
show(rel)
rel.test()
print " Cost of this relation: ", rel.cost()
print "Probability this relation applies to random D: ", rel.probapplies()
Cost of this relation: 1/2 Probability this relation applies to random D: 1/96
Cost of this relation: 1/2 Probability this relation applies to random D: 1/48
Cost of this relation: 1 Probability this relation applies to random D: 31/1440
Cost of this relation: 1 Probability this relation applies to random D: 31/2880
Cost of this relation: 1 Probability this relation applies to random D: 31/1440
Cost of this relation: 1 Probability this relation applies to random D: 31/2880
Cost of this relation: 1 Probability this relation applies to random D: 31/1440
Cost of this relation: 1 Probability this relation applies to random D: 31/2880
Cost of this relation: 1 Probability this relation applies to random D: 31/2880
Cost of this relation: 1 Probability this relation applies to random D: 31/1440
Cost of this relation: 1 Probability this relation applies to random D: 31/2880
Cost of this relation: 1 Probability this relation applies to random D: 31/2880
Cost of this relation: 1 Probability this relation applies to random D: 31/1440
Cost of this relation: 1 Probability this relation applies to random D: 31/2880
Cost of this relation: 1 Probability this relation applies to random D: 31/2880
Cost of this relation: 1 Probability this relation applies to random D: 31/1440
Cost of this relation: 1 Probability this relation applies to random D: 31/1440
Cost of this relation: 1 Probability this relation applies to random D: 31/1440
Cost of this relation: 1 Probability this relation applies to random D: 31/2880
Cost of this relation: 1 Probability this relation applies to random D: 31/2880
Cost of this relation: 1 Probability this relation applies to random D: 31/1440
Cost of this relation: 1 Probability this relation applies to random D: 31/2880
Cost of this relation: 1 Probability this relation applies to random D: 31/2880
Cost of this relation: 1 Probability this relation applies to random D: 31/2880
Cost of this relation: 1 Probability this relation applies to random D: 31/1440
Cost of this relation: 1 Probability this relation applies to random D: 31/1440
Cost of this relation: 1 Probability this relation applies to random D: 31/2880
Cost of this relation: 1 Probability this relation applies to random D: 31/1440
Cost of this relation: 1 Probability this relation applies to random D: 31/1440
Cost of this relation: 1 Probability this relation applies to random D: 31/2880
Cost of this relation: 1 Probability this relation applies to random D: 31/1440
Cost of this relation: 1 Probability this relation applies to random D: 31/1440