###################################################################### ## JPDA.txt Save this file as JPDA.txt to use it, # # stay in the # ## same directory, get into Maple (by typing: maple ) # ## and then type: read `JPDA.txt` # ## Then follow the instructions given there # ## # ## Written by Doron Zeilberger, Rutgers University , # ## DoronZeil at gmail dot com # ###################################################################### print(`Written: Oct. 2021: tested for Maple 2020 `): print(): print(`This is JPDA.txt, A Maple package`): print(`accompanying Shalosh B. Ekhad and Doron Zeilberger's article: `): print(` Automating John P. D'Angelo's method to study Complete Polynomial Sequences`): print(): print(`The most current version is available from:`): print(` http://sites.math.rutgers.edu/~zeilberg/tokhniot/JPDA.txt .`): print(`Please report all bugs to: DoronZeil at gmail dot com .`): print(): print(`For general help, and a list of the MAIN functions,`): print(` type "ezra();". For specific help type "ezra(procedure_name);" `): print(`For a list of the supporting functions type: ezra1();`): print(): ezra1:=proc() if args=NULL then print(`The SUPPORTING procedures are`): print(` Cutoffp, GFpG, Reps1, RGc1, Trunc `): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(` JPDA.txt: A Maple package automating John P. D'Angelo's method for studying complete polynomial sequences `): print(`The MAIN procedures are`): print(` Cutoff, CutoffV, DangeloReps, Mamar1, Reps, RGc, SmSeq, SpG`): elif nargs=1 and args[1]=Cutoff then print(`Cutoff(p,j,st,C,K)`): print(`inputs a polynomial p in the variable j, that maps positive integers to positive integers, as well as positive integres st and C, and a failry large integer K (for guessing)`): print(`outputs integers [N0,N1] such that`): print(`every integer >=N0 is expressible as a sum of DISTINCT images of p(j), with j>=st, in at least C different ways, together with an integer N1 (the "certificate") (using John P. D'Angelo's brilliant method)`): print(`such that checking that every integer between N0 and N1 is expressible in at least C different ways as distinct values of p(j), j>=st, implies that it is true for all intger >=N0, hence`): print(`proving the conjectured N0 rigorously. The output is the pair [N0,N1]. It if fails then it returns FAIL.`): print(`It then advises you to raise the K`): print(`Try:`): print(`Cutoff(j^2+j+1,j,0,1,1000);`): elif nargs=1 and args[1]=Cutoffp then print(`Cutoffp(p,j,N0): Given a polynomial p in j and an integer N0, finds the smallest N such that`): print(`p(j+1)<=2*p(j-1) and p{j)-p(j-3)>=N0 for all j>=N`): print(`Try: `): print(`Cutoffp(j^2+j+1,j,107);`): elif nargs=1 and args[1]=CutoffV then print(`CutoffV(p,j,st,C,K): a verbose form of Cutoff(p,j,st,C,K) (q.v.)`): print(`Try:`): print(`CutoffV(j^2+j+1,j,0,1,1000);`): elif nargs=1 and args[1]=DangeloReps then print(`DangeloReps(p,j,st,n,C,K): Same input as Reps(p,j,st,n), but also an integer C, also a large integer K (for guessing)`): print(`finds a set of (at least) C representations of n as sum of distinct p(j), j>=st (rather than the set all of possible representations)`): print(`using John D'Angelo's method.`): print(`Try:`): print(`DangeloReps(j^2+j+1,j,1,100,1,1000);`): elif nargs=1 and args[1]=GFpG then print(`GFpG(p,j,N,st): Given a polynomial p in j find the first N terms of Prod(1+q^p(j),j=st..infinity). Try:`): print(`GFpG(j^2+j+1,j,1000,0);`): print(`GFpG(j^2+j+1,j,1000,1);`): elif nargs=1 and args[1]=Mamar1 then print(`Mamar1(p,j,ST0,C0,K): inputs a polynomial p in the variable j, and positive integers ST0 and C0, and a large positve integer (for guessing)`): print(`outputs the smallest integer not expressible as a sum of distinct p(j) in at least C different ways`): print(`for j>=st. (and the "certificate"). Try:`): print(`Mamar1((j+1)*(j+2)/2,j,5,5,3000);`): elif nargs=1 and args[1]=Reps then print(`Reps(p,j,st,n): The set of ALL representations of n as sum of distinct values of the polynomial p j, starting at j=st. Try:`): print(`Reps(j^2+j+1,j,1,100);`): elif nargs=1 and args[1]=RGc then print(`RGc(p,x): inputs a polynomial p in the variable x, of degree n say, outputs true or false whether or not`): print(`p has the property that the sequence (p(1),p(2),...) is complete (i.e. that eventually every positive integer is expressible as a sum of DISCTINCT values of p(i) (i>=1)`): print(`Using Ron Graham's criterion. Try:`): print(`RGc(x^2+x+1,x);`): elif nargs=1 and args[1]=RGc1 then print(`RGc1(p,x): inputs a polynomial p in the variable x, of degree n say, outputs the list [a0,a1,..an] such that`): print(`p=a0+a1*binomial(x,1)+ ...+ an*binomial(x,n). Try:`): print(`RGc1(x^2+x+1,x);`): elif nargs=1 and args[1]=SmSeq then print(`SmSeq(p,j,M,K): Inputs a polynomial p in the variable j that passes the Ron Graham condition, a pos. integer M, and a fairly large positive integer K`): print(`outputs the smallest integer NOT represntable as a distinct sum of values of p(j) for j>=i for i=0,..., M. K is a guessing parameter that`): print(`makes sure that these values are rigorous. If K is not large enough the returned sequence may be shorter. Try:`): print(`SmSeq((j+2)*(j+1)/2,j,10,2000);`): elif nargs=1 and args[1]=SpG then print(`SpG(p,j,N1,st,C): The largest integer less than N1 that is not expressible as a sum of distinct values of the polynomial p(j) for j>=st in at least C ways. Try:`): print(`SpG(expand(binomial(j+2,2)),j,1000,0,1);`): elif nargs=1 and args[1]=Trunc then print(`Trunc(f,q,N): given a polynomial f of the variale q, returns truncated form, giving only terms up to q^n. Try`): print(`Trunc(mul(1+q^i),i=1..20),q,20);`): else print(`There is no such thing as`, args): fi: end: #Trunc(f,q,N): given a polynomial f of the variale q, returns truncated form, giving only terms up to q^n. Try #Trunc(mul(1+q^i),i=1..20),q,20); Trunc:=proc(f,q,N) local i:add(coeff(f,q,i)*q^i,i=0..N):end: #GFpG(p,j,N,st): Given a polynomial p in j find the first N terms of Prod(1+q^p(j),j=st..infinity). Try: #GFpG(j^2+j+1,j,1000,0); #GFpG(j^2+j+1,j,1000,1); GFpG:=proc(p,j,N,st) local j1,gu,q: gu:=1: for j1 from st while subs(j=j1,p)=st in at least C ways. Try: #SpG(expand(binomial(j+2,2)),j,1000,0,1); SpG:=proc(p,j,N1,st,C) local gu,j1: gu:=GFpG(p,j,N1,st): for j1 from nops(gu) by -1 to 1 while gu[j1]>=C do od: j1: end: #Cutoffp(p,j,N0): Given a polynomial p in j and an integer N0, finds the smallest N such that #p(j+1)<=2*p(j-1) and p{j)-p(j-3)>=C0 for all j>=N #Try: #Cutoff(j^2+j+1,j,107); Cutoffp:=proc(p,j,N0) local eq1,eq2,N,N1,N2,n: if not RGc(p,j) then print(`Ron Graham's criterion fails, does not exist`): RETURN(FAIL): fi: eq1:=2*subs(j=N-3,p)-subs(j=N+1,p): N1:=trunc(max(fsolve(eq1,N)))+1: if min(seq(subs(N=n,eq1),n=N1..N1+100))<=0 then RETURN(FAIL): fi: eq2:=expand(subs(j=N,p)-subs(j=N-3,p)-N0): N2:=trunc(max(fsolve(eq2,N)))+1: if min(seq(subs(N=n,eq2),n=N2..N2+100))<=0 then RETURN(FAIL): fi: subs(j=max(N1,N2)+1,p): end: #Cutoff(p,j,st,C,K): inputs a polynomial p in the variable j that maps pos. integers to pos. integres, finds the integers N0 and N1 such that #every integer >=N0 is expressible as a sum of DISTINCT images of p(j), together with an integer N1 (using John P. D'Angelo's brilliant method) #such that checking that every integer between N0 and N1 is expressible in such a way, implies that it is true for all intger >=N0, hence #proving the conjectured N0 rigorously. The output is the pair [N0,N1]. It if fails then it returns FAIL. #Try: #Cutoff(j^2+j+1,j,0,1,1000); Cutoff:=proc(p,j,st,C,K) local N0,N1: option remember: if not RGc(p,j) then print(`Ron Graham's criterion fails, does not exist`): RETURN(FAIL): fi: N0:=SpG(p,j,K,st,C)+1: if SpG(p,j,2*K,st,C)<>N0-1 then # print(`try a higher`, K): RETURN(FAIL): fi: N1:=Cutoffp(p,j,N0): if SpG(p,j,N1+1,st,C)<>N0-1 then RETURN(FAIL): else RETURN([N0,N1]): fi: end: #Reps(p,j,st,n): The set of all representations of n as sum of distinct values of the polynomial p in j with smallest p(st) and at most j1. Try: #Reps(j^2+j+1,j,1,100); Reps:=proc(p,j,st,n) local j2,n1,gu,gu1,gu11: option remember: if n=0 then RETURN({{}}): fi: if n<0 then RETURN({}): fi: if subs(j=st,p)>n then RETURN({}): fi: gu:={}: for j2 from st while subs(j=j2,p)<=n do n1:=n-subs(j=j2,p): gu1:=Reps(p,j,j2+1,n1): gu:=gu union {seq(gu11 union {j2},gu11 in gu1)}: od: gu: end: #DangeloReps(p,j,st,n,C,K): Same input as Reps(p,j,st,n), but also an integer C, also a large integer K (for guessing) #finds a set of (at least) C representations of n as sum of distinct p(j), j>=st (rather than the set all of possible representations) #using John D'Angelo's method. #Try: #DangeloReps(j^2+j+1,j,1,100,1,1000); DangeloReps:=proc(p,j,st,n,C,K) local gu,N0,N1,j1,N,n1,lu,lu1: option remember: gu:=Cutoff(p,j,st,C,K): if gu=FAIL then RETURN(FAIL): fi: N0:=gu[1]: N1:=gu[2]: if n=1) #Using Ron Graham's criterion. Try: #RGc(x^2+x+1,x);`): RGc:=proc(p,x) local L,i: L:=RGc1(p,x): if L[nops(L)]>0 and igcd(seq(numer(L[i]),i=1..nops(L)))=1 then true: else false: fi: end: #CutoffV(p,j,st,C,K): a verbose form of Cutoff(p,j,st,C,K) (q.v.) #every integer >=N0 is expressible as a sum of DISTINCT images of p(j), together with an integer N1 (using John P. D'Angelo's brilliant method) #such that checking that every integer between N0 and N1 is expressible in such a way, implies that it is true for all intger >=N0, hence #proving the conjectured N0 rigorously. The output is the pair [N0,N1]. It if fails then it returns FAIL. #Try: #CutoffV(j^2+j+1,j,0,1,1000); CutoffV:=proc(p,j,st,C,K) local gu,N0,N1,i,n,lu,y,eq1,eq2,N1a,N1b,N1c,N: print(``): print(`----------------------------------------------------------------------`): print(``): gu:=Cutoff(p,j,st,C,K): if gu=FAIL then RETURN(FAIL): fi: N0:=gu[1]: N1:=gu[2]: print(`Every integer >=`, N0, `can be represented in at least`, C, `different ways as sum of DISTINCT integer values of`, p, ` with j>=`, st): print(``): print(`By Shalosh B. Ekhad (with a little help from John D'Angelo and Ron Graham) `): print(``): print(`Theorem: See title`): print(``): print(`Proof: we first need a lemma `): print(``): print(`Lemma: The statement of the theorem is true for all n >=`, N0, `and <=`, N1): print(``): print(`Proof: Routine (left to the reader). Since there are`, N1-N0, `integers to check (we did it!), just for the sake of illustration let's pick three random integers >=`, N0, `and `, N1): for i from 1 to 3 do n:=rand(N0..N1)(): lu:=Reps(p,j,st,n): print(`For the integer`, n, `There are `, nops(lu), `such representations, let us only list`, C, `of them (after all that is all we need)`): print({op(1..C,lu)}): od: print(``): print(`We will now prove that if the integer y is larger than`, N1, `there always at least`, C, `such representations. The proof is by induction on y. Assume that the statement is true `): print(`for all integers >=`, N0, `and <`, y, `and we will prove that it is also true for y`): print(``): print(`Since p(j), j>=`, st, `is an increasing sequence there is a unique integer, let's call it N such that`): print(``): print(`p(N)=`,N1, `this N is >=`, N1c): print(``): print(`We express y as`): print(``): print(`y= (y-p(N-3))+p(N-3) `): print(`We claim that `): print(``): print(` (i): y-p(N-3)>=`, N0): print(``): print(` (ii): y-p(N-3)p(N)-p(N-3)=`, expand(subs(j=N,p)-subs(j=N-3,p))): eq2:=expand(subs(j=N,p)-subs(j=N-3,p)-N0): N1b:=trunc(max(fsolve(eq2,N)))+1: print(`But this is >=`,N0, ` for N >=`, N1b): print(``): eq1:=2*subs(j=N-3,p)-subs(j=N+1,p): N1a:=trunc(max(fsolve(eq1,N)))+1: print(`To prove (ii) note that since y<=p(N+1)`): print(``): print(`y-p(N-3) <= p(N+1)-p(N-3)=`, N1a): print(``): print(`The larger of these cutoffs integers`, N1a,N1b, `is `, N1c): print(``): print(`since the value of p(N) at N=`, N1c, ` is `, N1): print(``): print(`we are safe. QED. `): print(``): end: #Mamar1(p,j,ST0,C0,K): inputs a polynomial p in the variable j, and positive integers ST0 and C0, and a large positive integer K #outputs the smallest integer not expressible as a sum of distinct p(j) in at least C different ways #for j>=st. (and the "certificate"). Try: #Mamar1((j+1)*(j+2)/2,j,5,5,3000); Mamar1:=proc(p,j,ST0,C0,K) local st, C,gu: print(`The largest integer not representable as a distinct sum of values of p(j) for p(j)=`,p, `with j>=j0 in at least`, C, `different ways for j0 from 0 to`, ST0, `and C from 1 to`, C0): print(``): print(`By Shalosh B. Ekhad `): print(``): for st from 0 to ST0 do for C from 1 to C0 do print(``): gu:=Cutoff(p,j,st,C,K): if gu<>FAIL then print(`The smallest integer not representable as a sum of distinct values of the polynomial p(j)=`,p, `with j>=`, st, `in at least `, C , `different ways is`, gu[1]-1): print(``): print(`In order to prove this fact you need to check this for all positive integers <=`, gu[2], `that we did!`): fi: od: od: end: #SmSeq(p,j,M,K): Inputs a polynomial p in the variable j that passes the Ron Graham condition, a pos. integer M, and a fairly large positive integer K #outputs the smallest integer NOT represntable as a distinct sum of values of p(j) for j>=i for i=0,..., M. K is a guessing parameter that #makes sure that these values are rigorous. If K is not large enough the returned sequence may be shorter. Try: #SnSeq((j+2)*(j+1)/2,j,10,2000); SmSeq:=proc(p,j,M,K) local L,i,kha: L:=[]: for i from 0 to M do kha:=Cutoff(p,j,i,1,K): if kha=FAIL then RETURN(L): else L:=[op(L),kha[1]-1]: fi: od: L: end: