// Check5.magma // Version 2010-12-29 /* This Magma file is associated with the paper Vassil S. Dimitrov and Everett W. Howe, Lower bounds on the lengths of double-base representations, Proc. Amer. Math. Soc. (to appear). The programs in this file will complete the proof that the number g := 326552783 cannot be written as the sum of five integers of the form s*2^a*3^b, where s is 1 or -1 and a and b are integers. The C program Check5.c produces a list of pairs (p,y) of integers modulo m := 441033200890842920. Each p is of the form s3*2^a3*3^b3 (mod m), each y is of the form s2*3^b2 + s4*2^a4*3^b4 (mod m), and each y - p - g is of the form s1*2^a1 + s5*2^a5*3^b5 (mod m), and each (p,y) pair with these properties is included in the list. Thus each (p,y) pair gives us a representation g = - s1*2^a1 + s2*3^b2 - s3*2^a3*3^b3 + s4*2^a4*3^b4 - s5*2^a5*3^b5 (mod m) and every such representation (mod m) can be obtained from a (p,y) pair. Let n := 204*m. Given a representation of g as above, we will find all integers s*2^a*3^b modulo n that lift the individual summands. Then we will check to see whether the sum of the lifted summands is equal to g modulo n. As we will see, this will never be the case. */ /* Version 2010-09-01. Version history: 2010-09-01: First release version. Same as prerelease version, with slightly modified comments. 2010-12-29: Second release. Original release did computation with n = 204*m, which worked, and proved the result we want, but disagreed with the PAMS version of the paper, which said that we would do the computation modulo 408*m. The new value of n required changing exp2n from 149 to 150. */ // Everything between this comment and the next one is output from Check5.c pylist := [ [ 3779136 , 2706768111493088703 ], [ 3779136 , 4014643023858666303 ], [ 61956161762078016 , 1893254359898904615 ], [ 61956161762078016 , 3615390228741864399 ], [ 115381729471892472 , 1319602287611387007 ], [ 115381729471892472 , 2418145549877934423 ], [ 290713703858905176 , 150829445451683727 ], [ 290713703858905176 , 1553283361951380639 ], [ 338521367198215548 , 2325518511151843251 ], [ 338521367198215548 , 3720524386281464043 ], [ 520955145417542544 , 2424425646457411479 ], [ 520955145417542544 , 3889607617173213423 ], [ 559015983188399592 , 2462486484228268527 ], [ 559015983188399592 , 3889607617173213423 ], [ 606139612613841816 , 2080300810098329127 ], [ 606139612613841816 , 2773541420301375567 ], [ 623129763500011584 , 3077037828004747527 ], [ 623129763500011584 , 3990697101204129783 ], [ 951429678986154528 , 525039501950198775 ], [ 951429678986154528 , 2706768111493088703 ], [ 1204220557812941496 , 1319602287611387007 ], [ 1204220557812941496 , 3506984378218983447 ], [ 1262569657764874104 , 1122685399357652655 ], [ 1262569657764874104 , 1553283361951380639 ], [ 1474160922280027584 , 2080300810098329127 ], [ 1474160922280027584 , 3641562729967561335 ], [ 1660645380273728832 , 773046246362672295 ], [ 1660645380273728832 , 1893254359898904615 ], [ 1986997143627074664 , 927966961819480239 ], [ 1986997143627074664 , 2325518511151843251 ], [ 2167401532483074024 , 2773541420301375567 ], [ 2167401532483074024 , 3641562729967561335 ], [ 2259304591351732128 , 525039501950198775 ], [ 2259304591351732128 , 4014643023858666303 ], [ 2302763820079488912 , 2418145549877934423 ], [ 2302763820079488912 , 3506984378218983447 ], [ 2334269341218522672 , 1052907704430847407 ], [ 2334269341218522672 , 1629241252032430863 ], [ 2364861373252028568 , 1780841668872444687 ], [ 2364861373252028568 , 1899849341737076607 ], [ 2453907789300276216 , 1380441926113551495 ], [ 2453907789300276216 , 3077037828004747527 ], [ 2541183859153234872 , 1780841668872444687 ], [ 2541183859153234872 , 2076171827638282911 ], [ 2660191532017866792 , 1899849341737076607 ], [ 2660191532017866792 , 2076171827638282911 ], [ 3326205610688461776 , 1052907704430847407 ], [ 3326205610688461776 , 2621177521502369967 ], [ 3367567062499658472 , 1380441926113551495 ], [ 3367567062499658472 , 3990697101204129783 ], [ 3382003018756695456 , 927966961819480239 ], [ 3382003018756695456 , 3720524386281464043 ], [ 3382781249116688616 , 773046246362672295 ], [ 3382781249116688616 , 3615390228741864399 ], [ 3534867213363440568 , 2424425646457411479 ], [ 3534867213363440568 , 2462486484228268527 ], [ 3902539158290045232 , 1629241252032430863 ], [ 3902539158290045232 , 2621177521502369967 ], [ 4301148942156020112 , 150829445451683727 ], [ 4301148942156020112 , 1122685399357652655 ] ]; // Everything between this comment and the previous one is output from Check5.c m := 4441033200890842920; n := 408*m; g := 326552783; K := Integers(m); L := Integers(n); // Verify the highest exponents on 2 and 3 modulo m and n we must consider. exp2m := 147; exp2n := 150; exp3m := 434; exp3n := 435; assert 2^3 eq 2^exp2m mod m; assert 2^6 eq 2^exp2n mod n; assert 3^2 eq 3^exp3m mod m; assert 3^3 eq 3^exp3n mod n; P := {K!s*2^i*3^j : s in [-1,1], i in [0..exp2n-1], j in [0..exp3m-1]}; // Given an element of K, known to be the sum of a power of 2 and // an element of P, find all such representations. function P2reps(z) list := []; for i in [0..exp2m-1] do power2 := K!2^i; if z - power2 in P then list cat:= [[ power2,z-power2]]; end if; if z + power2 in P then list cat:= [[-power2,z+power2]]; end if; end for; return list; end function; // Given an element of K, known to be the sum of a power of 3 and // an element of P, find all such representations. function P3reps(z) list := []; for i in [0..exp3m-1] do power3 := K!3^i; if z - power3 in P then list cat:= [[ power3,z-power3]]; end if; if z + power3 in P then list cat:= [[-power3,z+power3]]; end if; end for; return list; end function; // Take the list of (p,y) pairs and produce the associated // representations of g modulo m. // y - p - g is an element of P2. replist := []; for py in pylist do p1 := py[1]; yreps := P3reps(py[2]); xreps := P2reps(py[2] - p1 - g); if #xreps*#yreps gt 1 then printf "Multiple representations from %o !\n", py; end if; for x in xreps, y in yreps do p3 := y[2]; p2 := x[2]; two := x[1]; three := y[1]; replist cat:= [[-two,three] cat Sort([-p1,-p2,p3])]; end for; end for; // Dedupe and sort the list of representations. replist := Sort([ a : a in Set(replist)]); /* For each representation in the list, we will want to lift the summands to the integers mod n. */ function liftP(z) // z is an element of K. // Find all elements of L of the form s*2^a*3^b that reduce to z. lifts := []; for s in [-1,1], i in [0..exp2n-1], j in [0..exp3n-1] do if z eq K!s*2^i*3^j then lifts cat:= [L!s*2^i*3^j]; end if; end for; return lifts; end function; liftedreps := []; for r in replist do r1 := liftP(r[1]); r2 := liftP(r[2]); r3 := liftP(r[3]); r4 := liftP(r[4]); r5 := liftP(r[5]); for a1 in r1, a2 in r2, a3 in r3, a4 in r4, a5 in r5 do liftedreps cat:= [ [a1,a2,a3,a4,a5] ]; end for; end for; liftedsums := [ &+z : z in liftedreps]; if not g in liftedsums then printf "The integer %o cannot be represented modulo %o\n",g,n; printf "as the sum of five integers of the form s*2^a*3^b,"; print " for integers a and b and a sign s."; else print "Something has gone horribly wrong!"; end if;