LinBox: you are running out of primes. 1000 coprime primes found

[vbraun]

Old issue, but still happens ocassionally. See also #12883 and https://groups.google.com/d/topic/linbox-use/SgsXVYM7u7s/discussion

sage -t --long src/sage/modular/modform/ambient.py
    Timed out
**********************************************************************
Tests run before process (pid=88588) timed out:
sage: chi = DirichletGroup(25,QQ).0; chi ## line 13 ##
Dirichlet character modulo 25 of conductor 5 mapping 2 |--> -1
sage: n = ModularForms(chi,2); n ## line 15 ##
Modular Forms space of dimension 6, character [-1] and weight 2 over Rational Field
sage: type(n) ## line 17 ##
<class 'sage.modular.modform.ambient_eps.ModularFormsAmbient_eps_with_category'>
sage: n.basis() ## line 22 ##
[
1 + O(q^6),
q + O(q^6),
q^2 + O(q^6),
q^3 + O(q^6),
q^4 + O(q^6),
q^5 + O(q^6)
]
sage: n.set_precision(20) ## line 34 ##
sage: n.basis() ## line 35 ##
[
1 + 10*q^10 + 20*q^15 + O(q^20),
q + 5*q^6 + q^9 + 12*q^11 - 3*q^14 + 17*q^16 + 8*q^19 + O(q^20),
q^2 + 4*q^7 - q^8 + 8*q^12 + 2*q^13 + 10*q^17 - 5*q^18 + O(q^20),
q^3 + q^7 + 3*q^8 - q^12 + 5*q^13 + 3*q^17 + 6*q^18 + O(q^20),
q^4 - q^6 + 2*q^9 + 3*q^14 - 2*q^16 + 4*q^19 + O(q^20),
q^5 + q^10 + 2*q^15 + O(q^20)
]
sage: m = ModularForms(Gamma1(20),2,GF(7)) ## line 47 ##
sage: loads(dumps(m)) == m ## line 48 ##
True
sage: m = ModularForms(GammaH(11,[4]), 2); m ## line 53 ##
Modular Forms space of dimension 2 for Congruence Subgroup Gamma_H(11) with H generated by [4] of weight 2 over Rational Field
sage: type(m) ## line 55 ##
<class 'sage.modular.modform.ambient_g1.ModularFormsAmbient_gH_Q_with_category'>
sage: m == loads(dumps(m)) ## line 57 ##
True
sage: sig_on_count() ## line 59 ##
0
sage: m = ModularForms(Gamma1(20),20); m ## line 102 ##
Modular Forms space of dimension 238 for Congruence Subgroup Gamma1(20) of weight 20 over Rational Field
sage: m.is_ambient() ## line 104 ##
True
sage: sig_on_count() ## line 106 ##
0
sage: m = ModularForms(Gamma1(20),100); m._repr_() ## line 127 ##
'Modular Forms space of dimension 1198 for Congruence Subgroup Gamma1(20) of weight 100 over Rational Field'
sage: m.rename('A big modform space') ## line 132 ##
sage: m ## line 133 ##
A big modform space
sage: m._repr_() ## line 135 ##
'Modular Forms space of dimension 1198 for Congruence Subgroup Gamma1(20) of weight 100 over Rational Field'
sage: sig_on_count() ## line 137 ##
0
sage: m = ModularForms(Gamma0(20),2) ## line 151 ##
sage: m._submodule_class() ## line 152 ##
<class 'sage.modular.modform.submodule.ModularFormsSubmodule'>
sage: sig_on_count() ## line 154 ##
0
sage: M = ModularForms(Gamma0(37),2) ## line 169 ##
sage: M.basis() ## line 170 ##
[
q + q^3 - 2*q^4 + O(q^6),
q^2 + 2*q^3 - 2*q^4 + q^5 + O(q^6),
1 + 2/3*q + 2*q^2 + 8/3*q^3 + 14/3*q^4 + 4*q^5 + O(q^6)
]
sage: M3 = M.change_ring(GF(3)) ## line 182 ##
sage: M3.basis() ## line 183 ##
[
1 + q^3 + q^4 + 2*q^5 + O(q^6),
q + q^3 + q^4 + O(q^6),
q^2 + 2*q^3 + q^4 + q^5 + O(q^6)
]
sage: sig_on_count() ## line 189 ##
0
sage: m = ModularForms(Gamma1(20),20) ## line 202 ##
sage: m.dimension() ## line 203 ##
238
sage: sig_on_count() ## line 205 ##
0
sage: ModularForms(25, 6).hecke_module_of_level(5) ## line 220 ##
Modular Forms space of dimension 3 for Congruence Subgroup Gamma0(5) of weight 6 over Rational Field
sage: ModularForms(Gamma1(4), 3).hecke_module_of_level(8) ## line 222 ##
Modular Forms space of dimension 7 for Congruence Subgroup Gamma1(8) of weight 3 over Rational Field
sage: ModularForms(Gamma1(4), 3).hecke_module_of_level(9) ## line 224 ##
sage: sig_on_count() ## line 228 ##
0
sage: ModularForms(22, 2)._degeneracy_raising_matrix(ModularForms(44, 2), 1) ## line 242 ##
[  1   0  -1  -2   0   0   0   0   0]
[  0   1   0  -2   0   0   0   0   0]
[  0   0   0   0   1   0   0   0  24]
[  0   0   0   0   0   1   0  -2  21]
[  0   0   0   0   0   0   1   3 -10]
sage: ModularForms(22, 2)._degeneracy_raising_matrix(ModularForms(44, 2), 2) ## line 248 ##
[0 1 0 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0]
[0 0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 1 0]
sage: sig_on_count() ## line 254 ##
0
sage: m = ModularForms(Gamma0(20),4) ## line 272 ##
sage: m.rank() ## line 273 ##
12
sage: m.dimension() ## line 275 ##
12
sage: sig_on_count() ## line 277 ##
0
sage: m = ModularForms(Gamma0(3),30) ## line 287 ##
sage: m.ambient_space() is m ## line 288 ##
True
sage: sig_on_count() ## line 290 ##
0
sage: ModularForms(11).is_ambient() ## line 301 ##
True
sage: CuspForms(11).is_ambient() ## line 303 ##
False
sage: sig_on_count() ## line 305 ##
0
sage: S = ModularForms(11,2) ## line 315 ##
sage: S.modular_symbols() ## line 316 ##
Modular Symbols space of dimension 3 for Gamma_0(11) of weight 2 with sign 0 over Rational Field
sage: S.modular_symbols(sign=1) ## line 318 ##
Modular Symbols space of dimension 2 for Gamma_0(11) of weight 2 with sign 1 over Rational Field
sage: S.modular_symbols(sign=-1) ## line 320 ##
Modular Symbols space of dimension 1 for Gamma_0(11) of weight 2 with sign -1 over Rational Field
sage: ModularForms(1,12).modular_symbols() ## line 325 ##
Modular Symbols space of dimension 3 for Gamma_0(1) of weight 12 with sign 0 over Rational Field
sage: sig_on_count() ## line 327 ##
0
sage: m = ModularForms(Gamma1(13),10) ## line 357 ##
sage: m.free_module() ## line 358 ##
Vector space of dimension 69 over Rational Field
sage: ModularForms(Gamma1(13),4, GF(49,'b')).free_module() ## line 360 ##
Vector space of dimension 27 over Finite Field in b of size 7^2
sage: M = ModularForms(Gamma1(57), 1); M ## line 367 ##
Modular Forms space of dimension (unknown) for Congruence Subgroup Gamma1(57) of weight 1 over Rational Field
sage: M.module() ## line 369 ##
Vector space of dimension 36 over Rational Field
sage: M.basis() ## line 371 ##
sage: sig_on_count() ## line 375 ##
0
sage: ModularForms(37).free_module() ## line 402 ##
Vector space of dimension 3 over Rational Field
sage: sig_on_count() ## line 404 ##
0
sage: M = ModularForms(1,12, prec=3) ## line 421 ##
sage: M.prec() ## line 422 ##
3
sage: M.basis() ## line 427 ##
[
q - 24*q^2 + O(q^3),
1 + 65520/691*q + 134250480/691*q^2 + O(q^3)
]
sage: M.prec(5) ## line 435 ##
5
sage: M.basis() ## line 437 ##
[
q - 24*q^2 + 252*q^3 - 1472*q^4 + O(q^5),
1 + 65520/691*q + 134250480/691*q^2 + 11606736960/691*q^3 + 274945048560/691*q^4 + O(q^5)
]
sage: sig_on_count() ## line 442 ##
0
sage: m = ModularForms(Gamma1(5),2) ## line 457 ##
sage: m.set_precision(10) ## line 458 ##
sage: m.basis() ## line 459 ##
[
1 + 60*q^3 - 120*q^4 + 240*q^5 - 300*q^6 + 300*q^7 - 180*q^9 + O(q^10),
q + 6*q^3 - 9*q^4 + 27*q^5 - 28*q^6 + 30*q^7 - 11*q^9 + O(q^10),
q^2 - 4*q^3 + 12*q^4 - 22*q^5 + 30*q^6 - 24*q^7 + 5*q^8 + 18*q^9 + O(q^10)
]
sage: m.set_precision(5) ## line 465 ##
sage: m.basis() ## line 466 ##
[
1 + 60*q^3 - 120*q^4 + O(q^5),
q + 6*q^3 - 9*q^4 + O(q^5),
q^2 - 4*q^3 + 12*q^4 + O(q^5)
]
sage: sig_on_count() ## line 472 ##
0
sage: ModularForms(Gamma1(13)).cuspidal_submodule() ## line 486 ##
Cuspidal subspace of dimension 2 of Modular Forms space of dimension 13 for Congruence Subgroup Gamma1(13) of weight 2 over Rational Field
sage: sig_on_count() ## line 489 ##
0
sage: m = ModularForms(Gamma1(13),2); m ## line 502 ##
Modular Forms space of dimension 13 for Congruence Subgroup Gamma1(13) of weight 2 over Rational Field
sage: m.eisenstein_submodule() ## line 504 ##
Eisenstein subspace of dimension 11 of Modular Forms space of dimension 13 for Congruence Subgroup Gamma1(13) of weight 2 over Rational Field
sage: sig_on_count() ## line 506 ##
0
sage: m = ModularForms(Gamma0(33),2); m ## line 527 ##
Modular Forms space of dimension 6 for Congruence Subgroup Gamma0(33) of weight 2 over Rational Field
sage: m.new_submodule() ## line 529 ##
Modular Forms subspace of dimension 1 of Modular Forms space of dimension 6 for Congruence Subgroup Gamma0(33) of weight 2 over Rational Field
sage: M = ModularForms(17,4) ## line 534 ##
sage: N = M.new_subspace(); N ## line 535 ##
Modular Forms subspace of dimension 4 of Modular Forms space of dimension 6 for Congruence Subgroup Gamma0(17) of weight 4 over Rational Field
sage: N.basis() ## line 537 ##
[
q + 2*q^5 + O(q^6),
q^2 - 3/2*q^5 + O(q^6),
q^3 + O(q^6),
q^4 - 1/2*q^5 + O(q^6)
]
sage: ModularForms(12,4).new_submodule() ## line 547 ##
Modular Forms subspace of dimension 1 of Modular Forms space of dimension 9 for Congruence Subgroup Gamma0(12) of weight 4 over Rational Field
sage: sig_on_count() ## line 561 ##
0
sage: m = ModularForms(Gamma0(23),2); m ## line 594 ##
Modular Forms space of dimension 3 for Congruence Subgroup Gamma0(23) of weight 2 over Rational Field
sage: m.basis() ## line 596 ##
[
q - q^3 - q^4 + O(q^6),
q^2 - 2*q^3 - q^4 + 2*q^5 + O(q^6),
1 + 12/11*q + 36/11*q^2 + 48/11*q^3 + 84/11*q^4 + 72/11*q^5 + O(q^6)
]
sage: m._q_expansion([1,2,0], 5) ## line 602 ##
q + 2*q^2 - 5*q^3 - 3*q^4 + O(q^5)
sage: sig_on_count() ## line 604 ##
0
sage: m = ModularForms(GammaH(11,[4]), 2); m ## line 623 ##
Modular Forms space of dimension 2 for Congruence Subgroup Gamma_H(11) with H generated by [4] of weight 2 over Rational Field
sage: m._dim_cuspidal() ## line 625 ##
1
sage: sig_on_count() ## line 627 ##
0
sage: m = ModularForms(GammaH(13,[4]), 2); m ## line 644 ##
Modular Forms space of dimension 3 for Congruence Subgroup Gamma_H(13) with H generated by [4] of weight 2 over Rational Field
sage: m._dim_eisenstein() ## line 646 ##
3
sage: sig_on_count() ## line 648 ##
0
sage: m = ModularForms(GammaH(11,[2]), 2); m._dim_new_cuspidal() ## line 668 ##
1
sage: sig_on_count() ## line 670 ##
0
sage: m = ModularForms(Gamma0(11), 4) ## line 686 ##
sage: m._dim_new_eisenstein() ## line 687 ##
0
sage: m = ModularForms(Gamma0(11), 2) ## line 689 ##
sage: m._dim_new_eisenstein() ## line 690 ##
1
sage: sig_on_count() ## line 692 ##
0
sage: m = ModularForms(Gamma0(22), 2) ## line 720 ##
sage: v = m.eisenstein_params(); v ## line 721 ##
[(Dirichlet character modulo 22 of conductor 1 mapping 13 |--> 1, Dirichlet character modulo 22 of conductor 1 mapping 13 |--> 1, 2), (Dirichlet character modulo 22 of conductor 1 mapping 13 |--> 1, Dirichlet character modulo 22 of conductor 1 mapping 13 |--> 1, 11), (Dirichlet character modulo 22 of conductor 1 mapping 13 |--> 1, Dirichlet character modulo 22 of conductor 1 mapping 13 |--> 1, 22)]
sage: type(v) ## line 723 ##
<class 'sage.structure.sequence.Sequence_generic'>
sage: sig_on_count() ## line 725 ##
0
sage: ModularForms(27,2).eisenstein_series() ## line 745 ##
[
q^3 + O(q^6),
q - 3*q^2 + 7*q^4 - 6*q^5 + O(q^6),
1/12 + q + 3*q^2 + q^3 + 7*q^4 + 6*q^5 + O(q^6),
1/3 + q + 3*q^2 + 4*q^3 + 7*q^4 + 6*q^5 + O(q^6),
13/12 + q + 3*q^2 + 4*q^3 + 7*q^4 + 6*q^5 + O(q^6)
]
sage: ModularForms(Gamma1(5),3).eisenstein_series() ## line 756 ##
[
-1/5*zeta4 - 2/5 + q + (4*zeta4 + 1)*q^2 + (-9*zeta4 + 1)*q^3 + (4*zeta4 - 15)*q^4 + q^5 + O(q^6),
q + (zeta4 + 4)*q^2 + (-zeta4 + 9)*q^3 + (4*zeta4 + 15)*q^4 + 25*q^5 + O(q^6),
1/5*zeta4 - 2/5 + q + (-4*zeta4 + 1)*q^2 + (9*zeta4 + 1)*q^3 + (-4*zeta4 - 15)*q^4 + q^5 + O(q^6),
q + (-zeta4 + 4)*q^2 + (zeta4 + 9)*q^3 + (-4*zeta4 + 15)*q^4 + 25*q^5 + O(q^6)
]
sage: eps = DirichletGroup(13).0^2 ## line 766 ##
sage: ModularForms(eps,2).eisenstein_series() ## line 767 ##
[
-7/13*zeta6 - 11/13 + q + (2*zeta6 + 1)*q^2 + (-3*zeta6 + 1)*q^3 + (6*zeta6 - 3)*q^4 - 4*q^5 + O(q^6),
q + (zeta6 + 2)*q^2 + (-zeta6 + 3)*q^3 + (3*zeta6 + 3)*q^4 + 4*q^5 + O(q^6)
]
sage: sig_on_count() ## line 772 ##
0
sage: m = ModularForms(11,4) ## line 779 ##
sage: m._compute_q_expansion_basis(5) ## line 780 ##
[q + 3*q^3 - 6*q^4 + O(q^5), q^2 - 4*q^3 + 2*q^4 + O(q^5), 1 + O(q^5), q + 9*q^2 + 28*q^3 + 73*q^4 + O(q^5)]
sage: sig_on_count() ## line 782 ##
0
sage: M = ModularForms(11, 2) ## line 800 ##
sage: M._compute_hecke_matrix(6) ## line 801 ##
[ 2  0]
[ 0 12]
sage: M = ModularForms(1, 512) ## line 812 ##
sage: t = M._compute_hecke_matrix(5)     # long time (2s) ## line 813 ##
sage: f = t.charpoly()                   # long time (4s) ## line 814 ##
you are running out of primes. 1000 coprime primes found

CC: @ClementPernet

Component: linear algebra

Keywords: random_fail

Issue created by migration from https://trac.sagemath.org/ticket/15535

[vbraun]

Changed keywords from none to random_fail

[jm58660]

comment:5

Following works for n=2..6. After several hours it fails for n=7 with same error message "1000 coprime primes". Failing function is eigenvalues(), but is this actually same bug?

from itertools import product
S = [0,1]
for n in range(2,10):
    smallest_value=1
    for m in product(*[S if i>j else [0] if i<j else [1] for i in range(n) for j in range(n)]):
        M = Matrix(ZZ,n,n,m)
        t = min( (M*M.transpose()).eigenvalues() )
        if t < smallest_value:
            smallest_value = t
            smallest_matrix=M
    print "N=", n, " Value", smallest_value   
    print smallest_matrix
    print '-'*10

This was tested on Sage 6.3. Also n=8 fails.

[bhutz]

Branch: u/bhutz/ticket/15535

[bhutz]

Changed branch from u/bhutz/ticket/15535 to none

[bhutz]

comment:7

Sorry, I had the wrong ticket checked out.

[roed314]

comment:8

I ran into this issue on Sage 6.4.1 trying to compute characteristic polynomials. I was computing the characteristic polynomial of hundreds of thousands of 3x3, 4x4, ..., 8x8 integer matrices, and at some point I got the following:

sage: A = matrix(ZZ, 4, 4, [50528, 38927, 19455, 31617, 58686, 39770, 31059, 21905, 13382, 35615, 18158, 11629, 25923, 12324, 51823, 27000])
sage: A.charpoly()
you are running out of primes. 1000 coprime primes found
1
sage: B = copy(A); B.charpoly()
x^4 - 135456*x^3 + 1234244249*x^2 + 17242461420805*x - 995535814473032365

[nathanncohen]

comment:9

Same happened with #17640.

[jdemeyer]

comment:10

Just got another report of this on sage-release...

[sagetrac-ehlen]

comment:13

I just ran into this when trying to compute newforms:

sage:  N_83_4 = Newforms(Gamma1(83),4,names='a')
you are running out of primes. 1000 coprime primes found

and sage ends up aborting to compute the decomposition in the end:

AssertionError: bug in decomposition; the sum of the dimensions (=0) of the factors must equal the dimension (800) of the acted on space:
Factors found: [

]
Space: Vector space of degree 902 and dimension 800 over Rational Field
Basis matrix:
800 x 902 dense matrix over Rational Field

[nexttime]

comment:14

From sage-devel:

Update: I think I finally found the bug that led some rare computations to hang forever: givaro's random iterator was seed from the 6 digits of the current time microseconds, and could, with proba 10^-6 be seeded with 0, and the congurential generator would then always output 0, causing the search for a non-zero krylov vector to hang forever!

This might be also a fix to https://github.com/sagemath/sage-prod/issues/15535

[...]

Clément

So the probability of failure is actually configurable! B)

[fchapoton]

comment:15

and what about this one ? also fixed by #24214 ? could be closed ?

[vbraun]

comment:16

I haven't seen this in a long time