// DoubleBase.magma // Version 2010-09-01 /* 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 file contains four functions: check2 check3 check4 is_provably_unrepresentable Running check2() and getting "true" as a result shows that every integer less than 103 can be written as the sum of two {2,3}-integers. Running is_provably_unrepresentable(103,2) and getting "true" as a result shows that 103 cannot be written as the sum of two {2,3}-integers. Running check3() and getting "true" as a result shows that every integer less than 4985 can be written as the sum of three {2,3}-integers. Running is_provably_unrepresentable(4985,3) and getting "true" as a result shows that 4985 cannot be written as the sum of three {2,3}-integers. Running check4() and getting "true" as a result shows that every integer less than 641687 can be written as the sum of four {2,3}-integers. Running is_provably_unrepresentable(641687,4) and getting "true" as a result shows that 641687 cannot be written as the sum of four {2,3}-integers. And running is_provably_unrepresentable(54425464,4) and getting "true" as a result is a step in proving that 326552783 cannot be written as the sum of five {2,3}-integers. */ /* Version 2010-09-01. Version history: 2010-09-01: Differs from prerelease version in that the sets of moduli used in is_provably_unrepresentable (the variable named "nset") are different. Also fixed a typo in the comments. */ /* ------------------------------------------------------------------------ check2(); This function verifies that all positive integers less than 103 can be written as the sum of two {2,3}-integers (as defined in the associated paper). It suffices to verify this for integers that are divisible by neither 2 nor 3. Three integers in this range are exceptional: They are of the form 2^s * 3^b - 1. Let T2 := {s * 2^a : a in [0..7], s in [-1,1] }; T3 := {s * 3^b : b in [0..4], s in [-1,1] }; For every n less than 103, coprime to 6, and not in the exceptional set, we calculate the intersection of the set T3 with the set {s + n : s in T2}. If this intersection is nonempty, then n can be written as the sum of an element of T2 and an element of T3. (This depends on T3 being closed under negation.) In turn, this means that n can be written as the sum of two {2,3}-integers. */ function check2(); goal := 103; exceptional := [2^5 * 3 - 1, 2^3 * 3^2 - 1, 2 * 3^3 - 1]; T2 := {s * 2^a : a in [0..7], s in [-1,1]}; T3 := {s * 3^b : b in [0..4], s in [-1,1]}; badlist := []; for n in [1..goal-1] do if GCD(n,6) eq 1 then if #({s + n : s in T2} meet T3) eq 0 then badlist cat:= [n]; end if; end if; end for; return #[n : n in badlist | not n in exceptional] eq 0; end function; /* ------------------------------------------------------------------------ check3(); This function verifies that all positive integers less than 4985 can be written as the sum of three {2,3}-integers (as defined in the associated paper). It suffices to verify this for integers that are divisible by neither 2 nor 3. Two integers in this range are exceptional: They are of the form 2^a * 3^b + 2^c * 3^d - 1. Let T2 := {s * 2^a : a in [0..16], s in [-1,1]}; T3 := {s * 3^b : b in [0..10], s in [-1,1]}; T := {s * 2^a * 3^b : a in [0..16], b in [0..10], s in [-1,1] | 2^a * 3^b le 2^5 * 3^7}; S := {r + s : r in T2, s in T3}; For every n less than 4985, coprime to 6, and not in the exceptional set, we calculate the intersection of the set T with the set {s + n : s in S}. If this intersection is nonempty, then n can be written as the sum of an element of S and an element of T. (This depends on S being closed under negation.) In turn, this means that n can be written as the sum of three {2,3}-integers. */ function check3(); goal := 4985; exceptional := [2^4 * 3^4 + 2^7 * 3^3 - 1, 2^3 * 3^2 + 2^7 * 3^3 - 1]; T2 := {s * 2^a : a in [0..16], s in [-1,1]}; T3 := {s * 3^b : b in [0..10], s in [-1,1]}; T := {s * 2^a * 3^b : a in [0..16], b in [0..10], s in [-1,1] | 2^a * 3^b le 2^5 * 3^7}; S := {r + s : r in T2, s in T3}; badlist := []; for n in [1..goal-1] do if GCD(n,6) eq 1 then if #({s + n : s in S} meet T) eq 0 then badlist cat:= [n]; end if; end if; end for; return #[n : n in badlist | not n in exceptional] eq 0; end function; /* ------------------------------------------------------------------------ check4(); This function verifies that all positive integers less than 641687 can be written as the sum of four {2,3}-integers (as defined in the associated paper). It suffices to verify this for integers that are divisible by neither 2 nor 3. Let T2 := [s * 2^a : a in [0..22], s in [-1,1] ]; T3 := [s * 3^b : b in [0..14], s in [-1,1] ]; T := [s * 2^a * 3^b : a in [0..22], b in [0..14], s in [-1,1] | 2^a * 3^b le 2^3 * 3^11]; and let S2 := {r + s : r in T, s in T2}; S3 := {r + s : r in T, s in T3}; For every n less than 641687 and coprime to 6, we calculate the intersection of the set S3 with the set {s + n : s in S2}. If this intersection is nonempty, then n can be written as the sum of an element of S2 and an element of S3. (This depends on S2 being closed under negation.) In turn, this means that n can be written as the sum of four {2,3}-integers. Timing information: It takes about 13 minutes to run this program on a 2.16 GHz Intel Core 2 Duo with 2 GB RAM. */ function check4(); goal := 641687; T2 := [s * 2^a : a in [0..22], s in [-1,1] ]; T3 := [s * 3^b : b in [0..14], s in [-1,1] ]; T := [s * 2^a * 3^b : a in [0..22], b in [0..14], s in [-1,1] | 2^a * 3^b le 2^3 * 3^11]; S2 := {r + s : r in T, s in T2}; S3 := {r + s : r in T, s in T3}; badlist := []; for n in [1..goal-1] do if GCD(n,6) eq 1 then if #({s + n : s in S2} meet S3) eq 0 then badlist cat:= [n]; end if; end if; end for; return #[n : n in badlist] eq 0; end function; /* ------------------------------------------------------------------------ is_provably_unrepresentable(goal, span : primitive := false, verbose := false, indent := ""); This function attempts to construct a proof that the integer is not expressible as the sum of integers of the form s*2^a*3^b, where s is either 1 or -1. If the function is able to construct such a proof, it returns "true", otherwise it returns "false". Note that a return value of "false" does *not* mean that cannot be so expressed; it just means that the techniques implemented in the function were insufficient to prove that it can be so expressed. If the optional flag is set to true, the function will attempt to show that cannot be expressed as the sum of the form described above, with the additional condition that the GCD of the summands is 1. The optional flag determines whether some diagnostic information is printed out. The optional variable is used internally. The algorithm we use is described in the paper mentioned above. Timing information and memory usage: On a 2.16 GHz Intel Core 2 Duo with 2 GB RAM, it takes 66 seconds and almost 1 GB of memory to run is_provably_unrepresentable(641687,4); */ function is_provably_unrepresentable(goal, span : primitive := false, verbose := false, indent := ""); if verbose then print indent, goal, span, primitive; end if; a := Valuation(goal,2); b := Valuation(goal,3); if span eq 1 then return AbsoluteValue(goal div (2^a*3^b)) ne 1; end if; if not primitive then // We're supposed to check for non-primitive solutions // as well as primitive solutions. for i in [0..a], j in [0..b] do bool := is_provably_unrepresentable(goal div (2^i*3^j), span : primitive := true, verbose := verbose, indent := indent cat " "); if not bool then return false; end if; end for; return true; end if; // Now check for primitive solutions that aren't doubly primitive. newgoal := Round(goal/6); if AbsoluteValue(newgoal*6 - goal) eq 1 then bool := is_provably_unrepresentable(newgoal, span-1 : primitive := false, verbose := verbose, indent := indent cat " "); if not bool then return false; end if; end if; // Now doubly-primitive solutions. case span: when 2: nlist := [ 1099511627760, 54610287600960, 952177069640160, 38391032183474880, 7409469211410651840, 1811941545963463911360]; when 3: nlist := [ 1099511627760, 54610287600960, 952177069640160, 38391032183474880, 7409469211410651840, 1811941545963463911360]; when 4: nlist := [ 1099511627760, 54610287600960, 952177069640160]; // We cut the list short for span = 4, because using the larger // values requires a lot of memory. end case; for n in nlist do if verbose then print indent, "---", n; end if; K := Integers(n); two := K!1; T2 := {two,-two}; repeat two*:=2; T2 join:= {two,-two}; until 2*two in T2; three := K!1; T3 := {three,-three}; repeat three*:=3; T3 join:= {three,-three}; until 3*three in T3; case span: when 2: if #({s + goal : s in T2} meet T3) eq 0 then return true; end if; when 3: products := {s*t : s in T2, t in T3}; sums := {s + t : s in T2, t in T3}; if #({s + goal : s in sums} meet products) eq 0 then return true; end if; when 4: products := {s*t : s in T2, t in T3}; P2 := {s + t : s in T2, t in products}; P3 := {s + t : s in T3, t in products}; if #({s + goal : s in P2} meet P3) eq 0 then return true; end if; end case; end for; return false; end function;