Given a finite subset A⊆Z and a multiset of non-zero integers Λ={λ1,…,λk}, the dilate sum Λ⋅A:=λ1⋅A+λ2⋅A+⋯+λk⋅A={λ1a1+⋯+λkak:a1,…,ak∈A}. For a non-zero real number r, say that Λ2r-dominates Λ1 if we can partition some of the elements of Λ2 into blocks summing to the elements of r⋅Λ1. Then for all finite subsets A⊆Z, Λ2⋅A contains a translate of r⋅(Λ1⋅A), and hence ∣Λ1⋅A∣≤∣Λ2⋅A∣ for all A. In a recent paper, Kravitz (arXiv:2606.27087) proves the converse: if Λ2 does not r-dominate Λ1 for any r, then there exists a finite set A satisfying ∣Λ1⋅A∣>∣Λ2⋅A∣. For example, {2,3,5,7} does not contain two disjoint subsets with a sum ratio of 7, and so there exists a finite A⊆Z for which ∣A+7⋅A∣>∣2⋅A+3⋅A+5⋅A+7⋅A∣. We extend Kravitz's method to apply it to multiple inequalities and multiple sets, showing that for multisets Λi,j with 1≤i≤k and 1≤j≤ℓ, there exist finite sets A1,…,Aℓ⊆Z such that for all 1≤i<k∣Λi,1⋅A1+⋯+Λi,ℓ⋅Aℓ∣>∣Λi+1,1⋅A1+⋯+Λi+1,ℓ⋅Aℓ∣ provided there do not exist indices 1≤i1<i2≤k and a non-zero scalar r such that Λi2,jr-dominates Λi1,j for all 1≤j≤ℓ. Along the way, we resolve the analogue of Nathanson's Problem 1 for his Theorem 4 (arXiv:1604.08940), as well as the problems in Section 1.4.3 of Kravitz's paper.
Introduction
For subsets A, B of an abelian group, we denote the sumset
A+B:={a+b:a∈A,b∈B}.
For a positive integer h, we denote the h-fold iterated sumset of A by
hA:=hA+⋯+A={a1+⋯+ah:a1,…,ah∈A},
and let 0A={0}.
For a non-zero integer λ, we denote the product of λ and A by λ⋅A:={λa:a∈A}. Given a multiset Λ={λ1,…,λk} of non-zero integers, we denote the Λ-dilate of A by
For a positive integer n, we write [n]:={1,…,n} and we denote the cyclic group of n elements by Zn:=Z/nZ. We will make use of the Chinese Remainder Theorem particularly in the statement that if p1,…,pk are distinct primes with product q, then Zq≅Zp1×⋯×Zpk.
Following Kravitz [1], for a fixed non-zero real number r, we will say that the multiset Λ2={λ2,1,…,λ2,ℓ}r-dominates Λ1={λ1,1,…,λ1,k} if there are disjoint subsets S1,…,Sk of [ℓ] such that
∀j∈[k]:rλ1,j=h∈Sj∑λ2,h,
and say Λ2 dominates Λ1 if Λ2r-dominates Λ1 for some non-zero real number r.
For example, {2,3,5}1-dominates {2,8}, −2-dominates {−1,−4} and 21-dominates {4,10}. If Λ2r-dominates Λ1 in this way, then for all subsets A of Z, Λ2⋅A contains a translate of r⋅(Λ1⋅A) and hence ∣Λ1⋅A∣≤∣Λ2⋅A∣. Kravitz [1] shows that domination is also necessary.
Theorem 1.1 (Theorem 1.2 of [1]). Let Λ1 and Λ2 be two multisets of non-zero integers. Then the dilate inequality ∣Λ1⋅A∣≤∣Λ2⋅A∣ holds for all finite sets A⊆Z if and only if Λ2 dominates Λ1.
Kravitz [1] also asks questions about multi-legged sumset races. In particular, for a fixed positive integer H he considers the ordered pairs (s,t) with 0≤t≤s≤H−1. Suppose that
(s1,t1),…,(sH(H+1)/2,tH(H+1)/2)
is an ordering of these pairs in which (s,t) occurs after both (s+1,t) and (if s>t) (s,t+1). Must there exist a finite set A⊆Z such that
The theorem above implies that no single one of the inequalities precludes the existence of such a set A. We slightly extend the method in [1] and show that there must indeed exist such an A. We in fact show that a collection of dilate sums can be put in any prescribed order, subject to domination requirements.
Theorem 1.2. Suppose Λ1,…,Λk are multisets of non-zero integers and suppose that for no i<j does Λj dominate Λi.
Then there exists a finite set A⊆Z such that
∣Λ1⋅A∣>∣Λ2⋅A∣>⋯>∣Λk⋅A∣.
Kravitz [1] also poses the following two-set version: Suppose that
(s1,t1),…,(sH2,tH2)
is some ordering of the ordered pairs (s,t) with 0≤s,t<H in which (s,t) always occurs after (s+1,t) and (s,t+1). Must there exist finite sets A,B⊆Z such that
∣s1A+t1B∣>∣s2A+t2B∣>⋯>∣sH2A+tH2B∣?
We give a positive answer to this question by extending Theorem 1.2 to multiple sets.
Theorem 1.3. Let Λi,j for 1≤i≤k, 1≤j≤ℓ be multisets of non-zero integers such that for no 1≤i1<i2≤k does there exist a non-zero real number r such that Λi2,jr-dominates Λi1,j for every 1≤j≤ℓ.
Then there exist finite sets A1,A2,…,Aℓ⊆Z such that
We adapt Kravitz’s construction [1] to prove Lemma 1.4.
For this section, fix multisets of non-zero integers Λ1,…,Λk and Λ∗ such that for no i does Λ∗ dominate Λi. Since every multiset dominates the empty multiset, we know that each Λi is non-empty.
Let the elements of Λi be {λi,1,…,λi,ki} and the elements of Λ∗ be {λ1∗,…,λm∗}.
Let us denote by C the set of coefficient pairs (i,j) where 1≤i≤k and 1≤j≤ki.
Lemma 2.1. Given any subset P of [m] and any choice of elements ch∈C for h∈P, there exist rationals (qc:c∈C) such that
j=1∑kiλi,jq(i,j)=1(1≤i≤k),
h∈P∑λh∗qch=0.
Proof. For all 1≤i≤k and 1≤j≤ki, let us write μi,j for the sum of λh∗ over all h∈P with ch=(i,j). Then
h∈P∑λh∗qch=i,j∑μi,jq(i,j).
Note that by the definition of domination, for no i is the vector (μi,1,…,μi,ki) a non-zero scalar multiple of (λi,1,…,λi,ki). Were it so, the disjoint sets {h∈P:ch=(i,j)}, 1≤j≤ki would witness that Λ∗ dominates Λi.
Define (qc:c∈C) by q(i,1)=λi,11 for all 1≤i≤k and q(i,j)=0 if j>1. Then clearly
j=1∑kiλi,jq(i,j)=1
for all 1≤i≤k. Let us write
S:=i,j∑μi,jq(i,j)=i∑λi,1μi,1.(1)
If S=0, we are done. Otherwise, there is some i with μi,1=0. For this i, there exists j with 2≤j≤ki such that λi,1μi,1=λi,jμi,j and then there exist rationals q,q′ such that
λi,1q+λi,jq′=0
μi,1q+μi,jq′=−S,
and if we replace q(i,1) with λi,11+q and q(i,j) with q′, we maintain ∑j=1kiλi,jq(i,j)=1, but we make ∑i,jμi,jq(i,j)=0 as required.
The following corollary records that the equations can be solved modulo every sufficiently large prime, uniformly over all choices of P and (ch)h∈P.
Corollary 2.2. For every sufficiently large prime p, every P⊆[m] and every choice of ch∈C for h∈P, there exist elements (qc:c∈C) of Zp such that
j=1∑kiλi,jq(i,j)=1(1≤i≤k),
h∈P∑λh∗qch=0.
Proof. Choose one rational solution for each pair (P,(ch:h∈P)). There are only finitely many denominators among these solutions, so they are invertible modulo every sufficiently large prime.
The following technical lemma provides the inductive step.
Lemma 2.3. Suppose N and q are positive integers with gcd(N,q)=1 and suppose that functions (ϕc:Zq→Zq:c∈C) satisfy
j=1∑kiλi,jϕ(i,j)(x)=x(x∈Zq,1≤i≤k).
Then for every ϵ>0, there exist a positive integer q′ coprime to Nq and functions (ϕc:Zq×Zq′→Zq×Zq′:c∈C) such that, writing π:Zq×Zq′→Zq for the projection to the first coordinate and defining E by
For each t∈T, choose a distinct prime pt>∣T∣ϵ−1 which does not divide Nq or λi,1 for any i and is large enough to satisfy Corollary 2.2.
For each such t=((x1,…,xm),(c1,…,cm)), we will define a function ϕt,c:Zq×Zpt→Zpt by defining the behaviour of ϕt,c(u,v) depending on u∈Zq.
If u∈{x1,…,xm}, set Pu={j∈[m]:xj=u} and apply Corollary 2.2 with Pu to get elements of Zpt(qc,u:c∈C) such that for all i∑j=1kiλi,jq(i,j),u=1, and ∑h∈Puλh∗qch,u=0. Then we define ϕt,c(u,v)=qc,uv for all v.
If u∈/{x1,…,xm}, define ϕt,(i,1)(u,v)=(λi,1)−1v for each i and ϕt,(i,j)(u,v)=0 for j>1.
Then one can check that for each element (u,v) of Zq×Zpt and for every i,
j=1∑kiλi,jϕt,(i,j)(u,v)=v.
Suppose y1,…,ym are elements of Zpt such that yi=yj whenever xi=xj. Then if, for u∈{x1,…,xm}, we write vu for the common value of the yh with h∈Pu,
Let q′=∏t∈Tpt and A=Zq×∏t∈TZpt, and define functions for c∈C by
ϕc(x,(xt:t∈T))=(ϕc(x),(ϕt,c(x,xt):t∈T)).
By the Chinese Remainder Theorem, ∏t∈TZpt≅Zq′, so we identify A with Zq×Zq′, while retaining the individual pt coordinates. Note that none of the pt divide Nq, so q′ is coprime to Nq.
By construction π∘ϕc=ϕc∘π and for every element a∈A, ∑j=1kiλi,jϕ(i,j)(a)=a for every 1≤i≤k.
Furthermore, for any element x∈E, x has an expression of the form ∑j=1mλj∗ϕcj(xj) where c1,…,cm∈C, x1,…,xm∈A and ∣{x1,…,xm}∣=∣{π(x1),…,π(xm)}∣.
Let t=((π(x1),…,π(xm)),(c1,…,cm)). The projection π is injective on {x1,…,xm}, so the pt-coordinates of the xi are constant on each set Pu. The vanishing identity above therefore shows that the pt-coordinate of x is 0. Thus E is contained in the union of the coordinate hyperplanes {a∈A:at=0} and hence by a simple union bound,
∣E∣≤t∑pt1∣A∣<ϵ∣A∣=ϵqq′.
□
Proof of Lemma 1.4. If m=0, let q be a prime that is larger than N, ϵ1 and the absolute value of all elements of the Λi and let A=Zq. Then for all i, Λi is non-empty (as it is not dominated by Λ∗=∅), and hence Λi⋅A=Zq, while ∣Λ∗⋅A∣=1<ϵq.
For m≥1, we will apply Lemma 2.3 m times with error ϵ/m. Let q0=1 and let (ϕ0,c:Zq0→Zq0:c∈C) all be the identity map. Then
j=1∑kiλi,jϕ0,(i,j)(x)=x(1≤i≤k).
Inductively, for 1≤z≤m, if we have defined qz−1 and (ϕz−1,c:c∈C), apply Lemma 2.3 with q=qz−1, with N unchanged and with error ϵ/m. Denote the resulting modulus by qz′, the new functions by ϕz,c and the exceptional set by Ez. Set qz=qz−1qz′ and identify Zqz with Zqz−1×Zqz′. Note that inductively each qz is coprime to N. Set q=qm and let ϕc=ϕm,c for c∈C. By construction
j=1∑kiλi,jϕ(i,j)(x)=x(1≤i≤k).
Then if we set A to be the set {ϕc(x):c∈C,x∈Zq}, we see that for all x∈Zq,
x=j=1∑kiλi,jϕ(i,j)(x)∈Λi⋅A,
so Λi⋅A=Zq for all i.
Now consider an element x of Λ∗⋅A. It has an expression of the form x=∑j=1mλj∗ϕcj(xj) where cj∈C and xj∈Zq. For 1≤j≤m, let πj:Zqj→Zqj−1 be the projection onto the first coordinate. Then for 0≤j≤m, define
ρj:=πj+1∘⋯∘πm:Zq→Zqj,
where ρm is the identity map.
Applying these projections to the elements x1,…,xm, we get a sequence of sets
Xj={ρj(x1),…,ρj(xm)}
with non-increasing sizes:
∣Xm∣≥∣Xm−1∣≥⋯≥∣X0∣.
Since ∣X0∣=1 and ∣Xm∣≤m, not all of the inequalities ∣Xz∣≥∣Xz−1∣ can be strict, so for some z, ∣Xz∣=∣Xz−1∣, which means the projection from Zqz to Zqz−1 is injective on Xz and hence
ρz(x)=j=1∑mλj∗ϕz,cj(ρz(xj))∈Ez,
where the equality follows from the compatibility of ϕr,c with the projections πr.
Thus x lies in ρz−1(Ez), which is of size ∣ρz−1(Ez)∣=∣Ez∣qzq<mϵq.
Every element of Λ∗⋅A lies in one of these m sets, so a simple union bound gives that
Proof of Theorem 1.5. Suppose Λ1,…,Λk and Φ1,…,Φℓ are multisets of non-zero integers. If Λi is empty then every Φj dominates Λi, and taking c>1 means there are no sets A with Λi⋅A=Zm.
If Φj dominates non-empty Λi, then its domination scalar is rational; write it as r=a/b for integers a,b. Then b⋅Φj 1-dominates a⋅Λi, and hence for every finite set A, (b⋅Φj)⋅A contains a translate of (a⋅Λi)⋅A.
If Λi⋅A=Zm, then
∣Φj⋅A∣≥∣b⋅(Φj⋅A)∣≥∣aZm∣=gcd(m,∣a∣)m≥∣a∣m.
Taking ϵ<∣a∣1 contradicts condition 2.
On the other hand, suppose that no Φj dominates any Λi for 1≤i≤k and 1≤j≤ℓ, and fix ϵ>0 and c>0. Let m0 be any prime greater than c and greater than the absolute value of every element of each Λi and set A0=Zm0. Since every Λi is non-empty and every one of its coefficients is invertible modulo m0, we have Λi⋅A0=Zm0.
For 1≤t≤ℓ, suppose inductively that we have found an integer mt−1>c and a subset At−1 of Zmt−1 such that
Λi⋅At−1=Zmt−1(1≤i≤k)
and
∣Φj⋅At−1∣<ϵmt−1(1≤j<t).
Then apply Lemma 1.4 with Λ∗=Φt, with error ϵ and with N=mt−1 to get a positive integer q and a subset A of Zq such that:
q is coprime to mt−1,
for all 1≤i≤k, Λi⋅A=Zq,
∣Φt⋅A∣<ϵq.
Set mt=qmt−1>c and At to be the image of At−1×A under the Chinese Remainder Theorem isomorphism Zmt−1×Zq≅Zmt.
For any multiset Λ, Λ⋅At≅(Λ⋅At−1)×(Λ⋅A), ∣Λ⋅A∣≤q and ∣Λ⋅At−1∣≤mt−1, so it follows that
Λi⋅At=Zmt(1≤i≤k) and
∣Φj⋅At∣=∣Φj⋅At−1∣∣Φj⋅A∣<(ϵmt−1)q=ϵmt(1≤j<t) and
∣Φt⋅At∣=∣Φt⋅At−1∣∣Φt⋅A∣<mt−1(ϵq)=ϵmt
so the induction is complete.
Set m=mℓ and A=Aℓ. Then m>c and A⊆Zm satisfies
Λi⋅A=Zm(1≤i≤k) and
∣Φj⋅A∣<ϵm(1≤j≤ℓ).
From finite cyclic groups to the integers
The proof of the following corollary follows a similar line to Theorem 1.5, but combines invocations of Lemma 1.4 in a slightly different way.
Corollary 3.1. Suppose Λ1,…,Λk are multisets of non-zero integers and suppose that for no i<j does Λj dominate Λi.
Then for all positive reals ϵ, there exists a positive integer q and a subset A of Zq such that for all 1≤i<k, ∣Λi+1⋅A∣<ϵ∣Λi⋅A∣.
Proof. If k=1, set q=1 and A=Z1 and both conditions are vacuous. Suppose k≥2.
By Lemma 1.4 with N=1 and error ϵ applied to Λ1 and Λ∗=Λ2, there exists a positive integer q1 and a subset A1 of Zq1 such that Λ1⋅A1=Zq1 and ∣Λ2⋅A1∣<ϵq1.
Suppose inductively for 2≤t<k we have found a positive integer qt−1 and a subset At−1 of Zqt−1 such that for all 1≤j<t,
∣Λj+1⋅At−1∣<ϵ∣Λj⋅At−1∣.
Choose ϵt such that ϵt∣Λt+1⋅At−1∣<ϵ∣Λt⋅At−1∣. Apply Lemma 1.4 with targets Λ1,…,Λt, exceptional multiset Λt+1, N=qt−1 and error ϵt. Then there exists a positive integer q coprime to qt−1 and a subset A of Zq such that Λj⋅A=Zq for all 1≤j≤t and ∣Λt+1⋅A∣<ϵtq.
Then set qt=qqt−1 and let At be the image of A×At−1 under the Chinese Remainder Theorem isomorphism Zq×Zqt−1≅Zqt. Then for all 1≤j<t,
Proof of Theorem 1.2. Apply Corollary 3.1 to the multisets Λ1,…,Λk with an error value ϵ we will specify later to get a subset A of Zq satisfying the required inequalities.
Let A∗ be the subset of the standard representatives {0,1,…,q−1} which is the preimage of A under the canonical projection map.
Then it is clear that for every multiset Λ of non-zero integers, Λ⋅A∗ contains at least one preimage of each element of Λ⋅A, so ∣Λ⋅A∗∣≥∣Λ⋅A∣.
Furthermore, if Λ={λ1,λ2,…,λh} and we write wt(Λ)=∣λ1∣+⋯+∣λh∣, then one can show that (2wt(Λ)+1)∣Λ⋅A∣≥∣Λ⋅A∗∣. If Λ is empty, both ∣Λ⋅A∣ and ∣Λ⋅A∗∣ are equal to 1. Otherwise, it is clear that for any element a∈Λ⋅A∗, ∣a∣<wt(Λ)q and hence there are at most 2wt(Λ) preimages of any given element of Λ⋅A.
Choose the error value ϵ above, so that it is smaller than 2wt(Λi)+11 for all 1≤i≤k,
In this section, we will use the multiset union operator ⊎. Given multisets Λ1 and Λ2, we denote the product
Λ1×Λ2=⨄j∈Λ1(j⋅Λ2).
For example, {1,1,2}×{2,4}={2,2,4,4,4,8}.
Lemma 4.1. Suppose Λi,j for 1≤i≤2 and 1≤j≤k are multisets of at most t non-zero integers, each of which has absolute value at most p.
Fix an integer N≥2tp+1 and for 1≤i≤2 define the multisets
Φi:=⨄j=1k(Λi,j×{N2kj,N(2k+1)j}).
For every non-zero real number r, the following are equivalent:
Φ1r-dominates Φ2
Λ1,jr-dominates Λ2,j for all j.
Proof. Given a multiset S, write σ(S):=∑s∈Ss.
First note that every integer z has at most one expression of the form z=∑i=0ℓaiNi with integer coefficients of absolute value at most tp and with non-zero leading coefficient: suppose we had two distinct such expressions z=∑i=0ℓ1aiNi=∑i=0ℓ2biNi and let i be the smallest index where ai=bi (padding the shorter sequence with zeroes if necessary), then N is a divisor of ai−bi, but 0<∣ai−bi∣≤2tp<N, which is impossible.
Now suppose we have submultisets S,T of Φ1 with σ(S)=Nhσ(T)=0 for some 1≤h≤k. Let us write
S=⨄j=1k(N2kj⋅Sj,1⊎N(2k+1)j⋅Sj,2)
T=⨄j=1k(N2kj⋅Tj,1⊎N(2k+1)j⋅Tj,2)
where Sj,v,Tj,v⊆Λ1,j. We can therefore write down two such expressions for σ(S)=Nhσ(T), namely:
σ(S)=j=1∑k(N2kjσ(Sj,1)+N(2k+1)jσ(Sj,2))
Nhσ(T)=j=1∑k(N2kj+hσ(Tj,1)+N(2k+1)j+hσ(Tj,2)).
These two expressions must be the same. Because 1≤h≤k, the only exponent that appears in both expressions is (2k+1)h. Indeed, writing E={2k,(2k+1)}×[k], one checks that E∩(E+h)={(2k+1)h} for 1≤h≤k. Thus, after discarding any zero-sum layers, S=N(2k+1)h⋅Sh,2 and T=N2kh⋅Th,1 for some submultisets Sh,2,Th,1 of Λ1,h with the same sum.
Now because Φ1r-dominates Φ2, there is a partition of some of the elements of Φ1 into non-empty disjoint submultisets, such that for each element λ of Φ2 there is a corresponding part whose elements sum to rλ.
Consider an element λ of Λ2,j. There are corresponding elements λN2kj and λN(2k+1)j of Φ2. Thus there are corresponding parts of the domination partition T and S, summing to rλN2kj and rλN(2k+1)j respectively.
After applying the preceding observation with h=j, the surviving low-layer portion has the form N2kjTj,1 with σ(Tj,1)=rλ. These Tj,1 remain disjoint as the occurrences of λ vary, because the original domination blocks were disjoint. Hence they witness that Λ1,jr-dominates Λ2,j.
Conversely, if every Λ1,jr-dominates Λ2,j, scale the witnessing blocks by N2kj and N(2k+1)j. The resulting blocks are disjoint across layers and witness that Φ1r-dominates Φ2. □
This allows us to determine exactly which inequalities of dilate sums of multiple sets can hold.
Proof of Theorem 1.3. Choose positive integers t and p such that every Λi,j has at most t elements, each of absolute value at most p. Then if we set N=2tp+1, Lemma 4.1 tells us that if we define
Φi=⨄j=1ℓ(Λi,j×{N2ℓj,N(2ℓ+1)j})
for 1≤i≤k, then the condition in the statement of the theorem implies that for no i1<i2 does Φi2 dominate Φi1.
Then Theorem 1.2 implies the existence of a finite set A such that ∣Φi⋅A∣>∣Φi+1⋅A∣ for all 1≤i<k. For 1≤j≤ℓ, set
Aj={N2ℓj,N(2ℓ+1)j}⋅A.
Then, for every 1≤i≤k,
Φi⋅A=Λi,1⋅A1+Λi,2⋅A2+⋯+Λi,ℓ⋅Aℓ.
The required inequalities for the Λi,j now follow from the inequalities for the Φi. □
Examples
We show here some examples of results that follow from Theorem 1.2. The first two give positive answers to questions which were asked in [1]. For non-negative integer h and multiset Λ, let us write
h⊙Λ:=⨄u=1hΛ,
where the union is empty when h=0.
In particular, h⊙{1} is the multiset containing h copies of 1. Note that h1⊙{1} dominates h2⊙{1} if and only if h1≥h2. Note also that for any finite set A, hA=(h⊙{1})⋅A.
Corollary 5.1.Suppose that(s1,t1),…,(sH2,tH2)is an ordering of the ordered pairs(s,t)with0≤s,t≤H−1in which(s,t)always occurs after(s+1,t)(assumings<H−1) and(s,t+1)(assumingt<H−1).
There exist finite sets A,B⊆Z such that
∣s1A+t1B∣>∣s2A+t2B∣>…>∣sH2A+tH2B∣.
Proof. For 1≤i≤H2, let Λi,1=si⊙{1} and Λi,2=ti⊙{1}. Then by the definition of the ordering (si,ti), if i<j, at least one of sj<si or tj<ti must hold. Hence for some v∈{1,2}, Λj,v does not dominate Λi,v.
Thus by Theorem 1.3, there exist finite sets A1,A2 such that for all 1≤i<H2, ∣(si⊙{1})⋅A1+(ti⊙{1})⋅A2∣>∣(si+1⊙{1})⋅A1+(ti+1⊙{1})⋅A2∣.
Setting A=A1 and B=A2, this can be rewritten as
∣s1A+t1B∣>∣s2A+t2B∣>…>∣sH2A+tH2B∣.
Corollary 5.2.Suppose that(s1,t1),…,(sH(H+1)/2,tH(H+1)/2)is an ordering of the ordered pairs(s,t)with0≤t≤s≤H−1in which(s,t)occurs after(s+1,t)(ifs<H−1) and after(s,t+1)(ifs>t).
Proof. For 1≤i≤H(H+1)/2, let Λi=(si⊙{1})⊎(ti⊙{−1}).
If Λir-dominates Λj for some non-zero real number r then there exists a way of partitioning some of the elements of Λi into parts that sum to r times the elements of Λj. We will show that i≤j.
If Λj is empty, then j=H(H+1)/2 and hence i≤j. We may therefore suppose that Λj is non-empty. Then the parts sum to either r or −r and hence r is a non-zero integer.
Counting the copies of 1 and −1 in the blocks, if r>0, then si≥rsj≥sj and ti≥rtj≥tj, so i≤j. If r<0, then si≥∣r∣tj≥tj and ti≥∣r∣sj≥sj. Since si≥ti and sj≥tj, this again gives si≥ti≥sj and ti≥sj≥tj, so i≤j.
Thus no Λi dominates Λj with j<i and Theorem 1.2 gives the existence of such an A.
Corollary 5.3.Suppose that(s1,t1),…,(sn,tn)are integer vectors with non-zero coordinates such that for alli=j, (si,ti)is not parallel to either(sj,tj)or(tj,sj).
Then there exists a finite set A⊆Z such that
∣s1⋅A+t1⋅A∣>∣s2⋅A+t2⋅A∣>…>∣sn⋅A+tn⋅A∣.
Proof. For 1≤i≤n, let Λi={si,ti}.
If Λir-dominates Λj, there is a way of partitioning some of the elements of Λi into blocks that sum to r times the elements of Λj. Since each block will need a non-zero sum, both blocks must be non-empty. Then, since Λi and Λj are the same size, each block is a singleton.
So either (si,ti)=r(sj,tj) or (si,ti)=r(tj,sj). Since (si,ti) is not parallel to either (sj,tj) or (tj,sj) when i=j, it follows that i=j.
Thus no Λi dominates any Λj with j<i and Theorem 1.2 gives the existence of such an A.
AI
The author used ChatGPT for a literature search and Codex for proofreading.
References
[1]N. Kravitz, Inequalities among higher-order difference sets, or, remarks on a construction of Ruzsa, arXiv:2606.27087, 2026.arxiv.org/abs/2606.27087
[2]M. B. Nathanson, Comparison estimates for linear forms in additive number theory, Journal of Number Theory 184 (2018), 1–26. arXiv:1604.08940.arxiv.org/abs/1604.08940