Loading implementation: /Users/mwg/Cloud/Sync/share/papers/skewmod/dilation/code/quantum_plane_factorization.sage ============================================================================== Example 1: reducible bound, central decomposition splits two linear factors m = 2 omega = -1 f = t^2 + t - x + x^2 bound(f) = X^2 + (2*T - 1)*X + T^2 - T factor(bound) = (X + T - 1) * (X + T) rough central-decomposition pieces: g1 = -t + x bound = X + T g2 = -t - 1 + x bound = X + T - 1 central bound: X^2 + (2*T - 1)*X + T^2 - T central factorization: (X + T - 1) * (X + T) central bound: X + T central factorization: X + T degree-one irreducible: -t + x degree-one irreducible: -t - 1 + x certified factorization: h1 = -t + x h2 = -t - 1 + x verified product equals f: True ============================================================================== Example 2: irreducible bound but reducible; modular stage recovers x-t m = 2 omega = -1 f = t^2 + x^2 bound(f) = X + T factor(bound) = X + T rough central-decomposition pieces: g1 = t^2 + x^2 bound = X + T central bound: X + T central factorization: X + T irreducible-bound piece needs modular search: t^2 + x^2 bound = X + T admissible right-factor degrees: [1] good central specialization T -> 2 good inert modular prime p = 3, k degree = 1 good inert modular prime p = 5, k degree = 1 starting Sage finite-field skew factor(uniform=False), degree=2, |lambda|=9 finished factor() in 0.058s; atom degrees = [1, 1] kept modular right divisor candidate #1 of degree 1 kept modular right divisor candidate #2 of degree 1 kept modular right divisor candidate #3 of degree 1 kept modular right divisor candidate #4 of degree 1 p = 3: modular degree-1 candidates = 4 starting Sage finite-field skew factor(uniform=False), degree=2, |lambda|=25 finished factor() in 0.008s; atom degrees = [1, 1] kept modular right divisor candidate #1 of degree 1 kept modular right divisor candidate #2 of degree 1 kept modular right divisor candidate #3 of degree 1 kept modular right divisor candidate #4 of degree 1 kept modular right divisor candidate #5 of degree 1 kept modular right divisor candidate #6 of degree 1 p = 5: modular degree-1 candidates = 6 certified specialized factor over L_A: theta + x certified specialized factor over L_A: -theta + x certified specialized factor over L_A: -3*theta - 4 + x certified specialized factor over L_A: 3*theta - 4 + x certified specialized factor over L_A: -3*theta + 4 + x certified specialized factor over L_A: 3*theta + 4 + x exact specialized candidates certified: 6 interpolated and certified upstairs factor: t + x modular stage certified right factor: t + x exact left quotient: t + x degree-one irreducible: t + x degree-one irreducible: t + x certified factorization: h1 = t + x h2 = t + x verified product equals f: True ============================================================================== Example 3: full two-level modular lift with interpolation in T, factor x-t*(T+1) m = 2 omega = -1 f = t^6 + 2*t^4 + t^2 + x^2 bound(f) = X + T^3 + 2*T^2 + T factor(bound) = X + T^3 + 2*T^2 + T rough central-decomposition pieces: g1 = t^6 + 2*t^4 + t^2 + x^2 bound = X + T^3 + 2*T^2 + T central bound: X + T^3 + 2*T^2 + T central factorization: X + T^3 + 2*T^2 + T irreducible-bound piece needs modular search: t^6 + 2*t^4 + t^2 + x^2 bound = X + T^3 + 2*T^2 + T admissible right-factor degrees: [1] good central specialization T -> 2 p = 3 rejected: central polynomial reduces to X good inert modular prime p = 5, k degree = 1 p = 7 rejected: not inert: y^m-A reducible over residue field good inert modular prime p = 11, k degree = 1 starting Sage finite-field skew factor(uniform=False), degree=2, |lambda|=25 finished factor() in 0.011s; atom degrees = [1, 1] kept modular right divisor candidate #1 of degree 1 kept modular right divisor candidate #2 of degree 1 kept modular right divisor candidate #3 of degree 1 kept modular right divisor candidate #4 of degree 1 kept modular right divisor candidate #5 of degree 1 kept modular right divisor candidate #6 of degree 1 p = 5: modular degree-1 candidates = 6 starting Sage finite-field skew factor(uniform=False), degree=2, |lambda|=121 finished factor() in 0.105s; atom degrees = [1, 1] kept modular right divisor candidate #1 of degree 1 kept modular right divisor candidate #2 of degree 1 kept modular right divisor candidate #3 of degree 1 kept modular right divisor candidate #4 of degree 1 kept modular right divisor candidate #5 of degree 1 kept modular right divisor candidate #6 of degree 1 kept modular right divisor candidate #7 of degree 1 kept modular right divisor candidate #8 of degree 1 kept modular right divisor candidate #9 of degree 1 kept modular right divisor candidate #10 of degree 1 kept modular right divisor candidate #11 of degree 1 kept modular right divisor candidate #12 of degree 1 p = 11: modular degree-1 candidates = 12 certified specialized factor over L_A: 3*theta + x certified specialized factor over L_A: 9*theta - 12 + x certified specialized factor over L_A: -9*theta - 12 + x certified specialized factor over L_A: -3*theta + x certified specialized factor over L_A: -9*theta + 12 + x certified specialized factor over L_A: 9*theta + 12 + x exact specialized candidates certified: 6 good central specialization T -> 3 p = 3 rejected: central polynomial reduces to X good inert modular prime p = 5, k degree = 1 good inert modular prime p = 7, k degree = 1 starting Sage finite-field skew factor(uniform=False), degree=2, |lambda|=25 finished factor() in 0.037s; atom degrees = [1, 1] kept modular right divisor candidate #1 of degree 1 kept modular right divisor candidate #2 of degree 1 kept modular right divisor candidate #3 of degree 1 kept modular right divisor candidate #4 of degree 1 kept modular right divisor candidate #5 of degree 1 kept modular right divisor candidate #6 of degree 1 p = 5: modular degree-1 candidates = 6 starting Sage finite-field skew factor(uniform=False), degree=2, |lambda|=49 finished factor() in 0.020s; atom degrees = [1, 1] kept modular right divisor candidate #1 of degree 1 kept modular right divisor candidate #2 of degree 1 kept modular right divisor candidate #3 of degree 1 kept modular right divisor candidate #4 of degree 1 kept modular right divisor candidate #5 of degree 1 kept modular right divisor candidate #6 of degree 1 kept modular right divisor candidate #7 of degree 1 kept modular right divisor candidate #8 of degree 1 p = 7: modular degree-1 candidates = 8 certified specialized factor over L_A: -4*theta + x certified specialized factor over L_A: 4*theta + x exact specialized candidates certified: 2 good central specialization T -> 5 p = 3 rejected: central polynomial reduces to X p = 5 rejected: central polynomial reduces to X good inert modular prime p = 7, k degree = 1 p = 11 rejected: not inert: y^m-A reducible over residue field good inert modular prime p = 13, k degree = 1 starting Sage finite-field skew factor(uniform=False), degree=2, |lambda|=49 finished factor() in 0.012s; atom degrees = [1, 1] kept modular right divisor candidate #1 of degree 1 kept modular right divisor candidate #2 of degree 1 kept modular right divisor candidate #3 of degree 1 kept modular right divisor candidate #4 of degree 1 kept modular right divisor candidate #5 of degree 1 kept modular right divisor candidate #6 of degree 1 kept modular right divisor candidate #7 of degree 1 kept modular right divisor candidate #8 of degree 1 p = 7: modular degree-1 candidates = 8 starting Sage finite-field skew factor(uniform=False), degree=2, |lambda|=169 finished factor() in 0.024s; atom degrees = [1, 1] kept modular right divisor candidate #1 of degree 1 kept modular right divisor candidate #2 of degree 1 kept modular right divisor candidate #3 of degree 1 kept modular right divisor candidate #4 of degree 1 kept modular right divisor candidate #5 of degree 1 kept modular right divisor candidate #6 of degree 1 kept modular right divisor candidate #7 of degree 1 kept modular right divisor candidate #8 of degree 1 kept modular right divisor candidate #9 of degree 1 kept modular right divisor candidate #10 of degree 1 kept modular right divisor candidate #11 of degree 1 kept modular right divisor candidate #12 of degree 1 kept modular right divisor candidate #13 of degree 1 kept modular right divisor candidate #14 of degree 1 p = 13: modular degree-1 candidates = 14 certified specialized factor over L_A: -6*theta + x certified specialized factor over L_A: 6*theta + x exact specialized candidates certified: 2 interpolated and certified upstairs factor: t^3 + t + x modular stage certified right factor: t^3 + t + x exact left quotient: t^3 + t + x degree-one irreducible: t^3 + t + x degree-one irreducible: t^3 + t + x certified factorization: h1 = t^3 + t + x h2 = t^3 + t + x verified product equals f: True ============================================================================== Example 4: irreducible bound and irreducible by degree-bound test m = 2 omega = -1 f = 1 + (t)*x + x^2 bound(f) = X^2 + (T + 2)*X + 1 factor(bound) = X^2 + (T + 2)*X + 1 rough central-decomposition pieces: g1 = 1 + (t)*x + x^2 bound = X^2 + (T + 2)*X + 1 central bound: X^2 + (T + 2)*X + 1 central factorization: X^2 + (T + 2)*X + 1 irreducible by degree-bound test: 1 + (t)*x + x^2 bound = X^2 + (T + 2)*X + 1 certified factorization: h1 = 1 + (t)*x + x^2 verified product equals f: True ============================================================================== Example 5: reducible bound; central stage splits off a linear and an irreducible piece m = 2 omega = -1 f = -t - 1 + (t^2 - t + 1)*x - x^2 + x^3 bound(f) = X^3 + (2*T + 1)*X^2 + (T^2 + T - 1)*X + T - 1 factor(bound) = (X + T - 1) * (X^2 + (T + 2)*X + 1) rough central-decomposition pieces: g1 = 1 + (t)*x + x^2 bound = X^2 + (T + 2)*X + 1 g2 = -t - 1 + x bound = X + T - 1 central bound: X^3 + (2*T + 1)*X^2 + (T^2 + T - 1)*X + T - 1 central factorization: (X + T - 1) * (X^2 + (T + 2)*X + 1) central bound: X^2 + (T + 2)*X + 1 central factorization: X^2 + (T + 2)*X + 1 irreducible by degree-bound test: 1 + (t)*x + x^2 bound = X^2 + (T + 2)*X + 1 degree-one irreducible: -t - 1 + x certified factorization: h1 = 1 + (t)*x + x^2 h2 = -t - 1 + x verified product equals f: True ============================================================================== Optional m=3 smoke test over Q(zeta_3) f = t^2 + t + ((-omega - 1)*t - 1)*x + x^2 bound(f) = X^2 + (-2*T - 1)*X + T^2 + T central pieces: [-t + x, -t - 1 + x] good inert modular prime p = 5, k degree = 2 chosen specialization T -> omega + 2 finite-field skew parent: Ore Polynomial Ring in x over Finite Field in lambda_bar_5 of size 5^6 twisted by lambda_bar_5 |--> lambda_bar_5^(5^4) finite-field skew element class: starting Sage finite-field skew factor(uniform=False), degree=1, |lambda|=15625 finished factor() in 0.001s; atom degrees = [1] one reduced finite-field skew factorization atom list: [x + lambda_bar_5^5 + 3*lambda_bar_5^4 + 2*lambda_bar_5^3 + 2*lambda_bar_5^2 + 4*lambda_bar_5 + 3] starting Sage finite-field skew factor(uniform=False), degree=1, |lambda|=15625 finished factor() in 0.000s; atom degrees = [1] kept modular right divisor candidate #1 of degree 1 m=3 smoke test passed Quantum-plane timed example suite Implementation: /Users/mwg/Cloud/Sync/share/papers/skewmod/dilation/code/quantum_plane_factorization.sage QP_LEVEL = all QP_VERBOSE = False QP_PRINT_POLYS = False ================================================================================================ C1: m=2 degree-2 central split into two linear factors ================================================================================================ stage: central only shape: central bound product of two linear factors deg_x(f) = 2 bound degree in X = 2 bound shape = deg1^1 * deg1^1 bound = X^2 + (2*T - 1)*X + T^2 - T bound irreducible? False factor degrees = 1+1 verified product equals input: True rough_degrees = 1+1 elapsed seconds: 0.012 ================================================================================================ C2: m=2 degree-5 central split into five linear factors ================================================================================================ stage: central only shape: five distinct linear central factors deg_x(f) = 5 bound degree in X = 5 bound shape = deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 bound = X^5 + (5*T - 30)*X^4 + (10*T^2 - 120*T + 273)*X^3 + (10*T^3 - 180*T^2 + 819*T - 820)*X^... bound irreducible? False factor degrees = 1+1+1+1+1 verified product equals input: True rough_degrees = 1+1+1+1+1 elapsed seconds: 0.069 ================================================================================================ C3: m=3 degree-5 central split into five linear factors ================================================================================================ stage: central only shape: five factors X-(T+c^3) deg_x(f) = 5 bound degree in X = 5 bound shape = deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 bound = X^5 + (-5*T - 100)*X^4 + (10*T^2 + 400*T + 2555)*X^3 + (-10*T^3 - 600*T^2 - 7665*T - 16... bound irreducible? False factor degrees = 1+1+1+1+1 verified product equals input: True rough_degrees = 1+1+1+1+1 elapsed seconds: 0.396 ================================================================================================ I1: m=3 irreducible-bound example g=(x^2-t)^2 ================================================================================================ stage: modular attempt + exact sparse certification shape: irreducible bound X^2-T deg_x(f) = 4 bound degree in X = 2 bound shape = deg2^1 bound = X^2 - T bound irreducible? True factor degrees = 2+2 verified product equals input: True constructed_factor = x^2 - t rough_degrees = 4 elapsed seconds: 0.850 ================================================================================================ I2: m=3 T-dependent irreducible-bound square ================================================================================================ stage: modular attempt + exact sparse certification shape: irreducible bound X^2 - T*(T+1)^3 notes: The factor x^2-t*(T+1) has nonconstant dependence on the central parameter T. deg_x(f) = 4 bound degree in X = 2 bound shape = deg2^1 bound = X^2 - T^4 - 3*T^3 - 3*T^2 - T bound irreducible? True factor degrees = 2+2 verified product equals input: True constructed_factor = x^2 - t*(T+1) rough_degrees = 4 elapsed seconds: 0.403 ================================================================================================ B1: factor irreducible central bound polynomial X^2-T ================================================================================================ stage: central irreducible + sparse exact shape: irreducible central polynomial, skew degree 6 deg_x(f) = 6 bound degree in X = 2 bound shape = deg2^1 bound = X^2 - T bound irreducible? True factor degrees = 2+2+2 verified product equals input: True identity = X^2-T=(x^2-t)^3 rough_degrees = 6 elapsed seconds: 0.031 ================================================================================================ S1: m=3 degree-8 central split into eight linear factors ================================================================================================ stage: central only shape: eight distinct central linear factors notes: This mainly stresses bound computation and repeated right-gcd splitting. deg_x(f) = 8 bound degree in X = 8 bound shape = deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 bound = X^8 + (-8*T - 784)*X^7 + (28*T^2 + 5488*T + 214918)*X^6 + (-56*T^3 - 16464*T^2 - 128950... bound irreducible? False factor degrees = 1+1+1+1+1+1+1+1 verified product equals input: True linear_factors = x-(t+c), c=0..7 rough_degrees = 1+1+1+1+1+1+1+1 elapsed seconds: 2.145 ================================================================================================ S2: m=3 degree-12 mixed central decomposition ================================================================================================ stage: central only + degree-bound tests shape: irreducible central factors of degrees 4,2 plus six linear factors notes: This is central-stage-complete but not just linear factors. deg_x(f) = 12 bound degree in X = 12 bound shape = deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg2^1 * deg4^1 bound = X^12 + (-6*T - 783)*X^11 + (-T^4 - 3*T^3 + 12*T^2 + 3914*T + 214135)*X^10 + (6*T^5 + 80... bound irreducible? False factor degrees = 1+1+1+1+1+1+2+4 verified product equals input: True constructed_degrees = 4+2+1+1+1+1+1+1 rough_degrees = 1+1+1+1+1+1+2+4 elapsed seconds: 148.660 ================================================================================================ S3: m=5 degree-6 central split over Q(zeta_5) ================================================================================================ stage: central only shape: six distinct central linear factors over K(T) notes: This increases the constant-field degree to phi(5)=4. deg_x(f) = 6 bound degree in X = 6 bound shape = deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 bound = X^6 + (-6*T - 4425)*X^5 + (15*T^2 + 22125*T + 4353175)*X^4 + (-20*T^3 - 44250*T^2 - 174... bound irreducible? False factor degrees = 1+1+1+1+1+1 verified product equals input: True constant_field = Q(zeta_5) rough_degrees = 1+1+1+1+1+1 elapsed seconds: 0.972 ================================================================================================ S4: m=3 degree-8 irreducible-bound square (x^4-t)^2 ================================================================================================ stage: modular attempt + exact sparse certification shape: irreducible bound X^4-T notes: Larger version of I1; finite-field budget is capped at p=5. deg_x(f) = 8 bound degree in X = 4 bound shape = deg4^1 bound = X^4 - T bound irreducible? True factor degrees = 4+4 verified product equals input: True constructed_factor = x^4 - t rough_degrees = 8 elapsed seconds: 599.347 ================================================================================================ S5: m=3 skew degree-15: factor irreducible bound X^5-T ================================================================================================ stage: central irreducible + sparse exact shape: irreducible central polynomial X^5-T notes: This pushes the irreducible-bound polynomial example to degree 15. deg_x(f) = 15 bound degree in X = 5 bound shape = deg5^1 bound = X^5 - T bound irreducible? True factor degrees = 5+5+5 verified product equals input: True identity = X^5-T=(x^5-t)^3 rough_degrees = 15 elapsed seconds: 0.049 ================================================================================================ TIMING SUMMARY ================================================================================================ id level m deg_x bound_deg_X expected_factor_degrees seconds status stage -- ------ - ----- ----------- ----------------------- ------- ------ -------------------------------------------- C1 core 2 2 2 1+1 0.012 OK central only C2 core 2 5 5 1+1+1+1+1 0.069 OK central only C3 core 3 5 5 1+1+1+1+1 0.396 OK central only I1 core 3 4 2 2+2 0.850 OK modular attempt + exact sparse certification I2 core 3 4 2 2+2 0.403 OK modular attempt + exact sparse certification B1 core 3 6 2 2+2+2 0.031 OK central irreducible + sparse exact S1 stress 3 8 8 1+1+1+1+1+1+1+1 2.145 OK central only S2 stress 3 12 12 1+1+1+1+1+1+2+4 148.660 OK central only + degree-bound tests S3 stress 5 6 6 1+1+1+1+1+1 0.972 OK central only S4 stress 3 8 4 4+4 599.347 OK modular attempt + exact sparse certification S5 stress 3 15 5 5+5+5 0.049 OK central irreducible + sparse exact Total wall time for selected examples: 752.934 seconds Detailed shapes: C1: m=2 degree-2 central split into two linear factors shape: m=2, deg_x=2, bound_deg_X=2, factors=1+1 bound shape: deg1^1 * deg1^1 time/status: 0.012 sec, OK C2: m=2 degree-5 central split into five linear factors shape: m=2, deg_x=5, bound_deg_X=5, factors=1+1+1+1+1 bound shape: deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 time/status: 0.069 sec, OK C3: m=3 degree-5 central split into five linear factors shape: m=3, deg_x=5, bound_deg_X=5, factors=1+1+1+1+1 bound shape: deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 time/status: 0.396 sec, OK I1: m=3 irreducible-bound example g=(x^2-t)^2 shape: m=3, deg_x=4, bound_deg_X=2, factors=2+2 bound shape: deg2^1 time/status: 0.850 sec, OK I2: m=3 T-dependent irreducible-bound square shape: m=3, deg_x=4, bound_deg_X=2, factors=2+2 bound shape: deg2^1 time/status: 0.403 sec, OK B1: factor irreducible central bound polynomial X^2-T shape: m=3, deg_x=6, bound_deg_X=2, factors=2+2+2 bound shape: deg2^1 time/status: 0.031 sec, OK S1: m=3 degree-8 central split into eight linear factors shape: m=3, deg_x=8, bound_deg_X=8, factors=1+1+1+1+1+1+1+1 bound shape: deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 time/status: 2.145 sec, OK S2: m=3 degree-12 mixed central decomposition shape: m=3, deg_x=12, bound_deg_X=12, factors=1+1+1+1+1+1+2+4 bound shape: deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg2^1 * deg4^1 time/status: 148.660 sec, OK S3: m=5 degree-6 central split over Q(zeta_5) shape: m=5, deg_x=6, bound_deg_X=6, factors=1+1+1+1+1+1 bound shape: deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 * deg1^1 time/status: 0.972 sec, OK S4: m=3 degree-8 irreducible-bound square (x^4-t)^2 shape: m=3, deg_x=8, bound_deg_X=4, factors=4+4 bound shape: deg4^1 time/status: 599.347 sec, OK S5: m=3 skew degree-15: factor irreducible bound X^5-T shape: m=3, deg_x=15, bound_deg_X=5, factors=5+5+5 bound shape: deg5^1 time/status: 0.049 sec, OK Wrote CSV summary to: /Users/mwg/Cloud/Sync/share/papers/skewmod/dilation/code/quantum_plane_timing_summary.csv