Bug (overflow?) in hypergeometric trace formula

[kedlaya]

I'm guessing an integer overflow, but we'll see.

sage: from sage.modular.hypergeometric_motive import HypergeometricData as HGData             
sage: H = HGData(cyclotomic=[[1,1,1,1,1],[10,2]])
sage: print(H.euler_factor(2,73))                                                             
-4297625829703557649*T^5 + 662995245372109*T^4 - 39356849890*T^3 + 7385410*T^2 - 4381*T + 1

So far so good. But increase the prime and havoc ensues! (There is no corresponding issue in Magma, so I assume this is just a local implementation issue.)

sage: print(H.euler_factor(2,79))
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
~/sage/local/lib/python3.9/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCaller.__call__ (build/cythonized/sage/misc/cachefunc.c:10303)()
   1942             try:
-> 1943                 return cache[k]
   1944             except TypeError:  # k is not hashable

KeyError: ((2, 79, False), ())

During handling of the above exception, another exception occurred:

KeyError                                  Traceback (most recent call last)
~/sage/local/lib/python3.9/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCaller.__call__ (build/cythonized/sage/misc/cachefunc.c:10303)()
   1942             try:
-> 1943                 return cache[k]
   1944             except TypeError:  # k is not hashable

KeyError: ((79, 2, 2, None, False), ())

During handling of the above exception, another exception occurred:

TypeError                                 Traceback (most recent call last)
<ipython-input-33-c3a725fd8304> in <module>
----> 1 print(H.euler_factor(Integer(2),Integer(79)))

~/sage/local/lib/python3.9/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCaller.__call__ (build/cythonized/sage/misc/cachefunc.c:10437)()
   1946                 return cache[k]
   1947         except KeyError:
-> 1948             w = self._instance_call(*args, **kwds)
   1949             cache[k] = w
   1950             return w

~/sage/local/lib/python3.9/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCaller._instance_call (build/cythonized/sage/misc/cachefunc.c:9916)()
   1822             True
   1823         """
-> 1824         return self.f(self._instance, *args, **kwds)
   1825 
   1826     cdef fix_args_kwds(self, tuple args, dict kwds):

~/sage/local/lib/python3.9/site-packages/sage/modular/hypergeometric_motive.py in euler_factor(self, t, p, cache_p)
   1622             raise ValueError("p^f cannot exceed 2^31")
   1623 
-> 1624         traces = [self.padic_H_value(p, i + 1, t, cache_p=cache_p)
   1625                   for i in range(bound)]
   1626 

~/sage/local/lib/python3.9/site-packages/sage/modular/hypergeometric_motive.py in <listcomp>(.0)
   1622             raise ValueError("p^f cannot exceed 2^31")
   1623 
-> 1624         traces = [self.padic_H_value(p, i + 1, t, cache_p=cache_p)
   1625                   for i in range(bound)]
   1626 

~/sage/local/lib/python3.9/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCaller.__call__ (build/cythonized/sage/misc/cachefunc.c:10437)()
   1946                 return cache[k]
   1947         except KeyError:
-> 1948             w = self._instance_call(*args, **kwds)
   1949             cache[k] = w
   1950             return w

~/sage/local/lib/python3.9/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCaller._instance_call (build/cythonized/sage/misc/cachefunc.c:9916)()
   1822             True
   1823         """
-> 1824         return self.f(self._instance, *args, **kwds)
   1825 
   1826     cdef fix_args_kwds(self, tuple args, dict kwds):

~/sage/local/lib/python3.9/site-packages/sage/modular/hypergeometric_motive.py in padic_H_value(self, p, f, t, prec, cache_p)
   1293         else:
   1294             gtab = gauss_table(p, f, prec, use_longs)
-> 1295             trcoeffs = hgm_coeffs(p, f, prec, gamma, m, D, gtab, prec, use_longs)
   1296         sigma = trcoeffs[p-2]
   1297         p_ring = sigma.parent()

~/sage/local/lib/python3.9/site-packages/sage/modular/hypergeometric_misc.pyx in sage.modular.hypergeometric_misc.hgm_coeffs (build/cythonized/sage/modular/hypergeometric_misc.c:3518)()
      6 from cysignals.signals cimport sig_check
      7 
----> 8 cpdef hgm_coeffs(long long p, int f, int prec, gamma, m, int D,
      9                  gtable, int gtable_prec, bint use_longs):
     10     r"""

~/sage/local/lib/python3.9/site-packages/sage/modular/hypergeometric_misc.pyx in sage.modular.hypergeometric_misc.hgm_coeffs (build/cythonized/sage/modular/hypergeometric_misc.c:2840)()
    109                             w1 = w1 * w2 % q2
    110                 else:
--> 111                     w2 = gtable[r1]
    112                     if gv > 0:
    113                         for j in range(gv):

TypeError: an integer is required

[kedlaya]

As suspected, this ended up being an issue about conversions between p-adics and fixed-precision integers (in this case long longs).

---

New commits:

​cc1ba6c

Correct use of long longs in hypergeometric_misc

[chapoton]

ok, let it be