betaFeedback

WorksMathematics

The Dilate Rollercoaster

Abstract

Given a finite subset A⊆ZA\subseteq\mathbb{Z} and a multiset of non-zero integers Λ={λ1,…,λk}Λ=\{λ_1, \ldots, λ_k\}, the dilate sum Λ⋅A:=λ1⋅A+λ2⋅A+⋯+λk⋅A={λ1a1+⋯+λkak:a1,…,ak∈A}.Λ\cdot A:=λ_1\cdot A+λ_2\cdot A+\cdots+λ_k\cdot A =\{λ_1a_1+\cdots+λ_ka_k: a_1, \ldots, a_k\in A\}. For a non-zero real number rr, say that Λ2Λ_2 rr-dominates Λ1Λ_1 if we can partition some of the elements of Λ2Λ_2 into blocks summing to the elements of r⋅Λ1r\cdotΛ_1. Then for all finite subsets A⊆ZA\subseteq\mathbb{Z}, Λ2⋅AΛ_2\cdot A contains a translate of r⋅(Λ1⋅A)r\cdot(Λ_1\cdot A), and hence ∣Λ1⋅A∣≤∣Λ2⋅A∣|Λ_1\cdot A|\le|Λ_2\cdot A| for all AA. In a recent paper, Kravitz (arXiv:2606.27087) proves the converse: if Λ2Λ_2 does not rr-dominate Λ1Λ_1 for any rr, then there exists a finite set AA satisfying ∣Λ1⋅A∣>∣Λ2⋅A∣|Λ_1\cdot A|>|Λ_2\cdot A|. For example, {2,3,5,7}\{2, 3, 5, 7\} does not contain two disjoint subsets with a sum ratio of 7, and so there exists a finite A⊆ZA\subseteq\mathbb{Z} for which ∣A+7⋅A∣>∣2⋅A+3⋅A+5⋅A+7⋅A∣|A+7\cdot A|>|2\cdot A+3\cdot A+5\cdot A+7\cdot A|. We extend Kravitz's method to apply it to multiple inequalities and multiple sets, showing that for multisets Λi,jΛ_{i,j} with 1≤i≤k1\le i\le k and 1≤j≤ℓ1\le j\le\ell, there exist finite sets A1,…,Aℓ⊆ZA_1, \ldots, A_\ell\subseteq\mathbb{Z} such that for all 1≤i<k1\le i<k ∣Λi,1⋅A1+⋯+Λi,ℓ⋅Aℓ∣>∣Λi+1,1⋅A1+⋯+Λi+1,ℓ⋅Aℓ∣|Λ_{i,1}\cdot A_1+\cdots+Λ_{i,\ell}\cdot A_\ell| >|Λ_{i+1,1}\cdot A_1+\cdots+Λ_{i+1,\ell}\cdot A_\ell| provided there do not exist indices 1≤i1<i2≤k1\le i_1<i_2\le k and a non-zero scalar rr such that Λi2,jΛ_{i_2,j} rr-dominates Λi1,jΛ_{i_1,j} for all 1≤j≤ℓ1\le j\le\ell. 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 AA, BB of an abelian group, we denote the sumset

A+B:={a+b:a∈A,b∈B}.A + B := \{a + b : a \in A, b \in B\}.

For a positive integer hh, we denote the hh-fold iterated sumset of AA by

hA:=A+⋯+A⏟h={a1+⋯+ah:a1,…,ah∈A},hA := \underbrace{A + \cdots+ A}_{h} = \{a_1 + \cdots+ a_h : a_1,\ldots,a_h \in A\},

and let 0A={0}0A = \{0\}.

For a non-zero integer λ\lambda, we denote the product of λ\lambda and AA by λ⋅A:={λa:a∈A}\lambda\cdot A := \{\lambda a : a \in A\}. Given a multiset Λ={λ1,…,λk}\Lambda= \{\lambda_1,\ldots,\lambda_k\} of non-zero integers, we denote the Λ\Lambda-dilate of AA by

Λ⋅A=λ1⋅A+λ2⋅A+⋯+λk⋅A={λ1a1+⋯+λkak:a1,…,ak∈A},\Lambda\cdot A = \lambda_1 \cdot A + \lambda_2 \cdot A + \cdots+ \lambda_k \cdot A = \{\lambda_1a_1 + \cdots+ \lambda_ka_k : a_1,\ldots,a_k \in A\},

and let ∅⋅A={0}\varnothing\cdot A = \{0\}.

For a positive integer nn, we write [n]:={1,…,n}[n] := \{1,\ldots,n\} and we denote the cyclic group of nn elements by Zn:=Z/nZ\mathbb{Z}_n := \mathbb{Z}/n\mathbb{Z}. We will make use of the Chinese Remainder Theorem particularly in the statement that if p1,…,pkp_1,\ldots,p_k are distinct primes with product qq, then Zq≅Zp1×⋯×Zpk\mathbb{Z}_q \cong\mathbb{Z}_{p_1} \times\cdots\times\mathbb{Z}_{p_k}.

Following Kravitz [1], for a fixed non-zero real number rr, we will say that the multiset Λ2={λ2,1,…,λ2,ℓ}\Lambda_2 = \{\lambda_{2,1},\ldots,\lambda_{2,\ell}\} rr-dominates Λ1={λ1,1,…,λ1,k}\Lambda_1 = \{\lambda_{1,1},\ldots,\lambda_{1,k}\} if there are disjoint subsets S1,…,SkS_1,\ldots,S_k of [ℓ][\ell] such that

∀j∈[k]:rλ1,j=∑h∈Sjλ2,h,\forall j \in[k] : r\lambda_{1,j} = \sum_{h\in S_j}\lambda_{2,h},

and say Λ2\Lambda_2 dominates Λ1\Lambda_1 if Λ2\Lambda_2 rr-dominates Λ1\Lambda_1 for some non-zero real number rr.

For example, {2,3,5}\{2,3,5\} 11-dominates {2,8}\{2,8\}, −2-2-dominates {−1,−4}\{-1,-4\} and 12\frac{1}{2}-dominates {4,10}\{4,10\}. If Λ2\Lambda_2 rr-dominates Λ1\Lambda_1 in this way, then for all subsets AA of Z\mathbb{Z}, Λ2⋅A\Lambda_2 \cdot A contains a translate of r⋅(Λ1⋅A)r \cdot(\Lambda_1 \cdot A) and hence ∣Λ1⋅A∣≤∣Λ2⋅A∣|\Lambda_1 \cdot A| \leq|\Lambda_2 \cdot A|. Kravitz [1] shows that domination is also necessary.

Theorem 1.1 (Theorem 1.2 of [1]). Let Λ1\Lambda_1 and Λ2\Lambda_2 be two multisets of non-zero integers. Then the dilate inequality ∣Λ1⋅A∣≤∣Λ2⋅A∣|\Lambda_1 \cdot A| \leq|\Lambda_2 \cdot A| holds for all finite sets A⊆ZA \subseteq\mathbb{Z} if and only if Λ2\Lambda_2 dominates Λ1\Lambda_1.

Kravitz [1] also asks questions about multi-legged sumset races. In particular, for a fixed positive integer HH he considers the ordered pairs (s,t)(s,t) with 0≤t≤s≤H−10 \leq t \leq s \leq H-1. Suppose that

(s1,t1),…,(sH(H+1)/2,tH(H+1)/2)(s_1,t_1),\ldots,(s_{H(H+1)/2},t_{H(H+1)/2})

is an ordering of these pairs in which (s,t)(s,t) occurs after both (s+1,t)(s+1,t) and (if s>ts>t) (s,t+1)(s,t+1). Must there exist a finite set A⊆ZA \subseteq\mathbb{Z} such that

∣s1A−t1A∣>∣s2A−t2A∣>⋯>∣sH(H+1)/2A−tH(H+1)/2A∣?|s_1A-t_1A|>|s_2A-t_2A|>\cdots>|s_{H(H+1)/2}A-t_{H(H+1)/2}A|?

The theorem above implies that no single one of the inequalities precludes the existence of such a set AA. We slightly extend the method in [1] and show that there must indeed exist such an AA. 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\Lambda_1,\ldots,\Lambda_k are multisets of non-zero integers and suppose that for no i<ji<j does Λj\Lambda_j dominate Λi\Lambda_i.

Then there exists a finite set A⊆ZA \subseteq\mathbb{Z} such that

∣Λ1⋅A∣>∣Λ2⋅A∣>⋯>∣Λk⋅A∣.|\Lambda_1 \cdot A|>|\Lambda_2 \cdot A|>\cdots>|\Lambda_k \cdot A|.

Kravitz [1] also poses the following two-set version: Suppose that

(s1,t1),…,(sH2,tH2)(s_1,t_1),\ldots,(s_{H^2},t_{H^2})

is some ordering of the ordered pairs (s,t)(s,t) with 0≤s,t<H0 \leq s,t < H in which (s,t)(s,t) always occurs after (s+1,t)(s+1,t) and (s,t+1)(s,t+1). Must there exist finite sets A,B⊆ZA,B \subseteq\mathbb{Z} such that

∣s1A+t1B∣>∣s2A+t2B∣>⋯>∣sH2A+tH2B∣?|s_1A+t_1B|>|s_2A+t_2B|>\cdots>|s_{H^2}A+t_{H^2}B|?

We give a positive answer to this question by extending Theorem 1.2 to multiple sets.

Theorem 1.3. Let Λi,j\Lambda_{i,j} for 1≤i≤k1 \leq i \leq k, 1≤j≤ℓ1 \leq j \leq\ell be multisets of non-zero integers such that for no 1≤i1<i2≤k1 \leq i_1 < i_2 \leq k does there exist a non-zero real number rr such that Λi2,j\Lambda_{i_2,j} rr-dominates Λi1,j\Lambda_{i_1,j} for every 1≤j≤ℓ1 \leq j \leq\ell.

Then there exist finite sets A1,A2,…,Aℓ⊆ZA_1,A_2,\ldots,A_\ell\subseteq\mathbb{Z} such that

∣Λ1,1⋅A1+Λ1,2⋅A2+⋯+Λ1,ℓ⋅Aℓ∣>⋯>∣Λk,1⋅A1+Λk,2⋅A2+⋯+Λk,ℓ⋅Aℓ∣.|\Lambda_{1,1}\cdot A_1+\Lambda_{1,2}\cdot A_2+\cdots+\Lambda_{1,\ell}\cdot A_\ell|>\cdots>|\Lambda_{k,1}\cdot A_1+\Lambda_{k,2}\cdot A_2+\cdots+\Lambda_{k,\ell}\cdot A_\ell|.

The key ingredient in these results will be the following lemma, which is an extension of Proposition 3.1 from [1].

Lemma 1.4. Suppose Λ1,…,Λk\Lambda_1,\ldots,\Lambda_k and Λ∗\Lambda^* are multisets of non-zero integers and that for no ii does Λ∗\Lambda^* dominate Λi\Lambda_i.

Then for all positive integers NN and positive reals ϵ\epsilon, there exists a positive integer qq and a subset AA of Zq\mathbb{Z}_q such that:

  • qq is coprime to NN,

  • for all 1≤i≤k1 \leq i \leq k, Λi⋅A=Zq\Lambda_i \cdot A = \mathbb{Z}_q,

  • ∣Λ∗⋅A∣<ϵq\lvert\Lambda^* \cdot A\rvert< \epsilon q.

This result will also allow us to give an exact characterisation of when the conclusion of Theorem 4 of Nathanson [2] holds.

Theorem 1.5. Suppose Λ1,…,Λk\Lambda_1,\ldots,\Lambda_k and Φ1,…,Φℓ\Phi_1,\ldots,\Phi_\ell are multisets of non-zero integers.

The following are equivalent:

  1. No Φj\Phi_j dominates any Λi\Lambda_i for 1≤i≤k1 \leq i \leq k and 1≤j≤ℓ1 \leq j \leq\ell.

  2. For every ϵ>0\epsilon> 0 and c>0c > 0, there exist an integer m>cm > c and a subset AA of Zm\mathbb{Z}_m such that

Λi⋅A=Zm(1≤i≤k)and∣Φj⋅A∣<ϵm(1≤j≤ℓ).\Lambda_i \cdot A = \mathbb{Z}_m \quad(1 \leq i \leq k) \quad\text{and}\quad\lvert\Phi_j \cdot A\rvert< \epsilon m \quad(1 \leq j \leq\ell).

In § 2, we prove Lemma 1.4 and extend it to Theorem 1.5. Then in § 3 we deduce Theorem 1.2 from Lemma 1.4, and we extend it to Theorem 1.3 in § 4. Finally, in § 5, we give some specific examples, solving the aforementioned problems of Kravitz [1].

Key construction

We adapt Kravitz’s construction [1] to prove Lemma 1.4.

For this section, fix multisets of non-zero integers Λ1,…,Λk\Lambda_1,\ldots,\Lambda_k and Λ∗\Lambda^* such that for no ii does Λ∗\Lambda^* dominate Λi\Lambda_i. Since every multiset dominates the empty multiset, we know that each Λi\Lambda_i is non-empty.

Let the elements of Λi\Lambda_i be {λi,1,…,λi,ki}\{\lambda_{i,1},\ldots,\lambda_{i,k_i}\} and the elements of Λ∗\Lambda^* be {λ1∗,…,λm∗}\{\lambda^*_1,\ldots,\lambda^*_m\}.

Let us denote by CC the set of coefficient pairs (i,j)(i,j) where 1≤i≤k1 \leq i \leq k and 1≤j≤ki1 \leq j \leq k_i.

Lemma 2.1. Given any subset PP of [m][m] and any choice of elements ch∈Cc_h \in C for h∈Ph \in P, there exist rationals (qc:c∈C)(q_c:c \in C) such that

∑j=1kiλi,jq(i,j)=1(1≤i≤k),\sum_{j=1}^{k_i}\lambda_{i,j}q_{(i,j)}=1 \quad(1 \leq i \leq k),
∑h∈Pλh∗qch=0.\sum_{h\in P}\lambda^*_h q_{c_h}=0.

Proof. For all 1≤i≤k1 \leq i \leq k and 1≤j≤ki1 \leq j \leq k_i, let us write μi,j\mu_{i,j} for the sum of λh∗\lambda^*_h over all h∈Ph \in P with ch=(i,j)c_h=(i,j). Then

∑h∈Pλh∗qch=∑i,jμi,jq(i,j).\sum_{h\in P}\lambda^*_h q_{c_h}=\sum_{i,j}\mu_{i,j}q_{(i,j)}.

Note that by the definition of domination, for no ii is the vector (μi,1,…,μi,ki)(\mu_{i,1},\ldots,\mu_{i,k_i}) a non-zero scalar multiple of (λi,1,…,λi,ki)(\lambda_{i,1},\ldots,\lambda_{i,k_i}). Were it so, the disjoint sets {h∈P:ch=(i,j)}\{h \in P:c_h=(i,j)\}, 1≤j≤ki1 \leq j \leq k_i would witness that Λ∗\Lambda^* dominates Λi\Lambda_i.

Define (qc:c∈C)(q_c:c \in C) by q(i,1)=1λi,1q_{(i,1)}=\frac{1}{\lambda_{i,1}} for all 1≤i≤k1 \leq i \leq k and q(i,j)=0q_{(i,j)}=0 if j>1j>1. Then clearly

∑j=1kiλi,jq(i,j)=1\sum_{j=1}^{k_i}\lambda_{i,j}q_{(i,j)}=1

for all 1≤i≤k1 \leq i \leq k. Let us write

S:=∑i,jμi,jq(i,j)=∑iμi,1λi,1.(1)S:=\sum_{i,j}\mu_{i,j}q_{(i,j)}=\sum_i\frac{\mu_{i,1}}{\lambda_{i,1}}. \tag*{(1)}

If S=0S=0, we are done. Otherwise, there is some ii with μi,1≠0\mu_{i,1}\ne0. For this ii, there exists jj with 2≤j≤ki2\le j\le k_i such that μi,1λi,1≠μi,jλi,j\frac{\mu_{i,1}}{\lambda_{i,1}}\ne\frac{\mu_{i,j}}{\lambda_{i,j}} and then there exist rationals q,q′q,q' such that

λi,1q+λi,jq′=0\lambda_{i,1}q+\lambda_{i,j}q'=0
μi,1q+μi,jq′=−S,\mu_{i,1}q+\mu_{i,j}q'=-S,

and if we replace q(i,1)q_{(i,1)} with 1λi,1+q\frac{1}{\lambda_{i,1}}+q and q(i,j)q_{(i,j)} with q′q', we maintain ∑j=1kiλi,jq(i,j)=1\sum_{j=1}^{k_i}\lambda_{i,j}q_{(i,j)}=1, but we make ∑i,jμi,jq(i,j)=0\sum_{i,j}\mu_{i,j}q_{(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 PP and (ch)h∈P(c_h)_{h\in P}.

Corollary 2.2. For every sufficiently large prime pp, every P⊆[m]P\subseteq[m] and every choice of ch∈Cc_h\in C for h∈Ph\in P, there exist elements (qc:c∈C)(q_c:c\in C) of Zp\mathbb{Z}_p such that

∑j=1kiλi,jq(i,j)=1(1≤i≤k),\sum_{j=1}^{k_i}\lambda_{i,j}q_{(i,j)}=1\quad(1\le i\le k),
∑h∈Pλh∗qch=0.\sum_{h\in P}\lambda_h^*q_{c_h}=0.

Proof. Choose one rational solution for each pair (P,(ch:h∈P))(P,(c_h:h\in 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 NN and qq are positive integers with gcd⁡(N,q)=1\gcd(N,q)=1 and suppose that functions (ϕc:Zq→Zq:c∈C)(\phi_c:\mathbb{Z}_q\to\mathbb{Z}_q:c\in C) satisfy

∑j=1kiλi,jϕ(i,j)(x)=x(x∈Zq,1≤i≤k).\sum_{j=1}^{k_i}\lambda_{i,j}\phi_{(i,j)}(x)=x\quad(x\in\mathbb{Z}_q,1\le i\le k).

Then for every ϵ>0\epsilon>0, there exist a positive integer q′q' coprime to NqNq and functions (ϕ~c:Zq×Zq′→Zq×Zq′:c∈C)(\widetilde{\phi}_c:\mathbb{Z}_q\times\mathbb{Z}_{q'}\to\mathbb{Z}_q\times\mathbb{Z}_{q'}:c\in C) such that, writing π:Zq×Zq′→Zq\pi:\mathbb{Z}_q\times\mathbb{Z}_{q'}\to\mathbb{Z}_q for the projection to the first coordinate and defining EE by

E:={∑j=1mλj∗ϕ~cj(xj):c1,…,cm∈C, x1,…,xm∈Zq×Zq′, ∣{x1,…,xm}∣=∣{π(x1),…,π(xm)}∣},E:=\left\{\sum_{j=1}^{m}\lambda_j^*\widetilde{\phi}_{c_j}(x_j):c_1,\ldots,c_m\in C,\ x_1,\ldots,x_m\in\mathbb{Z}_q\times\mathbb{Z}_{q'},\ \left|\{x_1,\ldots,x_m\}\right|=\left|\{\pi(x_1),\ldots,\pi(x_m)\}\right|\right\},

the following hold:

  • π∘ϕ~c=ϕc∘π\pi\circ\widetilde{\phi}_c=\phi_c\circ\pi for every c∈Cc\in C,

  • ∑j=1kiλi,jϕ~(i,j)(x)=x(x∈Zq×Zq′,1≤i≤k)\sum_{j=1}^{k_i}\lambda_{i,j}\widetilde{\phi}_{(i,j)}(x)=x\quad(x\in\mathbb{Z}_q\times\mathbb{Z}_{q'},1\le i\le k),

  • ∣E∣<ϵqq′|E|<\epsilon qq'.

Proof. Define

T:={((x1,…,xm),(c1,…,cm)):c1,…,cm∈C,x1,…,xm∈Zq}.T:=\{((x_1,\ldots,x_m),(c_1,\ldots,c_m)):c_1,\ldots,c_m\in C,x_1,\ldots,x_m\in\mathbb{Z}_q\}.

For each t∈Tt\in T, choose a distinct prime pt>∣T∣ϵ−1p_t>|T|\epsilon^{-1} which does not divide NqNq or λi,1\lambda_{i,1} for any ii and is large enough to satisfy Corollary 2.2.

For each such t=((x1,…,xm),(c1,…,cm))t=((x_1,\ldots,x_m),(c_1,\ldots,c_m)), we will define a function ϕt,c:Zq×Zpt→Zpt\phi_{t,c}:\mathbb{Z}_q\times\mathbb{Z}_{p_t}\to\mathbb{Z}_{p_t} by defining the behaviour of ϕt,c(u,v)\phi_{t,c}(u,v) depending on u∈Zqu\in\mathbb{Z}_q.

If u∈{x1,…,xm}u\in\{x_1,\ldots,x_m\}, set Pu={j∈[m]:xj=u}P_u=\{j\in[m]:x_j=u\} and apply Corollary 2.2 with PuP_u to get elements of Zpt\mathbb{Z}_{p_t} (qc,u:c∈C)(q_{c,u}:c\in C) such that for all ii ∑j=1kiλi,jq(i,j),u=1\sum_{j=1}^{k_i}\lambda_{i,j}q_{(i,j),u}=1, and ∑h∈Puλh∗qch,u=0\sum_{h\in P_u}\lambda_h^*q_{c_h,u}=0. Then we define ϕt,c(u,v)=qc,uv\phi_{t,c}(u,v)=q_{c,u}v for all vv.

If u∉{x1,…,xm}u\notin\{x_1,\ldots,x_m\}, define ϕt,(i,1)(u,v)=(λi,1)−1v\phi_{t,(i,1)}(u,v)=(\lambda_{i,1})^{-1}v for each ii and ϕt,(i,j)(u,v)=0\phi_{t,(i,j)}(u,v)=0 for j>1j>1.

Then one can check that for each element (u,v)(u,v) of Zq×Zpt\mathbb{Z}_q\times\mathbb{Z}_{p_t} and for every ii,

∑j=1kiλi,jϕt,(i,j)(u,v)=v.\sum_{j=1}^{k_i}\lambda_{i,j}\phi_{t,(i,j)}(u,v)=v.

Suppose y1,…,ymy_1,\ldots,y_m are elements of Zpt\mathbb{Z}_{p_t} such that yi=yjy_i=y_j whenever xi=xjx_i=x_j. Then if, for u∈{x1,…,xm}u\in\{x_1,\ldots,x_m\}, we write vuv_u for the common value of the yhy_h with h∈Puh\in P_u,

∑j=1mλj∗ϕt,cj(xj,yj)=∑u∑h∈Puλh∗ϕt,ch(u,vu)=∑u∑h∈Puλh∗qch,uvu=0.\sum_{j=1}^{m}\lambda_j^*\phi_{t,c_j}(x_j,y_j)=\sum_u\sum_{h\in P_u}\lambda_h^*\phi_{t,c_h}(u,v_u)=\sum_u\sum_{h\in P_u}\lambda_h^*q_{c_h,u}v_u=0.

Let q′=∏t∈Tptq'=\prod_{t\in T}p_t and A=Zq×∏t∈TZptA=\mathbb{Z}_q\times\prod_{t\in T}\mathbb{Z}_{p_t}, and define functions for c∈Cc\in C by

ϕ~c(x,(xt:t∈T))=(ϕc(x),(ϕt,c(x,xt):t∈T)).\widetilde{\phi}_c(x,(x_t:t\in T))=(\phi_c(x),(\phi_{t,c}(x,x_t):t\in T)).

By the Chinese Remainder Theorem, ∏t∈TZpt≅Zq′\prod_{t\in T}\mathbb{Z}_{p_t}\cong\mathbb{Z}_{q'}, so we identify AA with Zq×Zq′\mathbb{Z}_q\times\mathbb{Z}_{q'}, while retaining the individual ptp_t coordinates. Note that none of the ptp_t divide NqNq, so q′q' is coprime to NqNq.

By construction π∘ϕ~c=ϕc∘π\pi\circ\widetilde{\phi}_c=\phi_c\circ\pi and for every element a∈Aa\in A, ∑j=1kiλi,jϕ~(i,j)(a)=a\sum_{j=1}^{k_i}\lambda_{i,j}\widetilde{\phi}_{(i,j)}(a)=a for every 1≤i≤k1\leq i\leq k.

Furthermore, for any element x∈Ex\in E, xx has an expression of the form ∑j=1mλj∗ϕ~cj(xj)\sum_{j=1}^{m}\lambda_j^*\widetilde{\phi}_{c_j}(x_j) where c1,…,cm∈Cc_1,\ldots,c_m\in C, x1,…,xm∈Ax_1,\ldots,x_m\in A and ∣{x1,…,xm}∣=∣{π(x1),…,π(xm)}∣|\{x_1,\ldots,x_m\}|=|\{\pi(x_1),\ldots,\pi(x_m)\}|.

Let t=((π(x1),…,π(xm)),(c1,…,cm))t=((\pi(x_1),\ldots,\pi(x_m)),(c_1,\ldots,c_m)). The projection π\pi is injective on {x1,…,xm}\{x_1,\ldots,x_m\}, so the ptp_t-coordinates of the xix_i are constant on each set PuP_u. The vanishing identity above therefore shows that the ptp_t-coordinate of xx is 00. Thus EE is contained in the union of the coordinate hyperplanes {a∈A:at=0}\{a\in A:a_t=0\} and hence by a simple union bound,

∣E∣≤∑t1pt∣A∣<ϵ∣A∣=ϵqq′.|E|\leq\sum_t\frac{1}{p_t}|A|<\epsilon|A|=\epsilon qq'.

□

Proof of Lemma 1.4. If m=0m=0, let qq be a prime that is larger than NN, 1ϵ\frac{1}{\epsilon} and the absolute value of all elements of the Λi\Lambda_i and let A=ZqA=\mathbb{Z}_q. Then for all ii, Λi\Lambda_i is non-empty (as it is not dominated by Λ∗=∅\Lambda^*=\varnothing), and hence Λi⋅A=Zq\Lambda_i\cdot A=\mathbb{Z}_q, while ∣Λ∗⋅A∣=1<ϵq|\Lambda^*\cdot A|=1<\epsilon q.

For m≥1m\geq1, we will apply Lemma 2.3 mm times with error ϵ/m\epsilon/m. Let q0=1q_0=1 and let (ϕ0,c:Zq0→Zq0:c∈C)(\phi_{0,c}:\mathbb{Z}_{q_0}\to\mathbb{Z}_{q_0}:c\in C) all be the identity map. Then

∑j=1kiλi,jϕ0,(i,j)(x)=x(1≤i≤k).\sum_{j=1}^{k_i}\lambda_{i,j}\phi_{0,(i,j)}(x)=x\quad(1\leq i\leq k).

Inductively, for 1≤z≤m1\leq z\leq m, if we have defined qz−1q_{z-1} and (ϕz−1,c:c∈C)(\phi_{z-1,c}:c\in C), apply Lemma 2.3 with q=qz−1q=q_{z-1}, with NN unchanged and with error ϵ/m\epsilon/m. Denote the resulting modulus by qz′q'_z, the new functions by ϕz,c\phi_{z,c} and the exceptional set by EzE_z. Set qz=qz−1qz′q_z=q_{z-1}q'_z and identify Zqz\mathbb{Z}_{q_z} with Zqz−1×Zqz′\mathbb{Z}_{q_{z-1}}\times\mathbb{Z}_{q'_z}. Note that inductively each qzq_z is coprime to NN. Set q=qmq=q_m and let ϕc=ϕm,c\phi_c=\phi_{m,c} for c∈Cc\in C. By construction

∑j=1kiλi,jϕ(i,j)(x)=x(1≤i≤k).\sum_{j=1}^{k_i}\lambda_{i,j}\phi_{(i,j)}(x)=x \qquad(1\le i\le k).

Then if we set AA to be the set {ϕc(x):c∈C,x∈Zq}\{\phi_c(x):c\in C,x\in\mathbb{Z}_q\}, we see that for all x∈Zqx\in\mathbb{Z}_q,

x=∑j=1kiλi,jϕ(i,j)(x)∈Λi⋅A,x=\sum_{j=1}^{k_i}\lambda_{i,j}\phi_{(i,j)}(x)\in\Lambda_i\cdot A,

so Λi⋅A=Zq\Lambda_i\cdot A=\mathbb{Z}_q for all ii.

Now consider an element xx of Λ∗⋅A\Lambda^*\cdot A. It has an expression of the form x=∑j=1mλj∗ϕcj(xj)x=\sum_{j=1}^{m}\lambda_j^*\phi_{c_j}(x_j) where cj∈Cc_j\in C and xj∈Zqx_j\in\mathbb{Z}_q. For 1≤j≤m1\le j\le m, let πj:Zqj→Zqj−1\pi_j:\mathbb{Z}_{q_j}\to\mathbb{Z}_{q_{j-1}} be the projection onto the first coordinate. Then for 0≤j≤m0\le j\le m, define

ρj:=πj+1∘⋯∘πm:Zq→Zqj,\rho_j:=\pi_{j+1}\circ\cdots\circ\pi_m:\mathbb{Z}_q\to\mathbb{Z}_{q_j},

where ρm\rho_m is the identity map.

Applying these projections to the elements x1,…,xmx_1,\ldots,x_m, we get a sequence of sets

Xj={ρj(x1),…,ρj(xm)}X_j=\{\rho_j(x_1),\ldots,\rho_j(x_m)\}

with non-increasing sizes:

∣Xm∣≥∣Xm−1∣≥⋯≥∣X0∣.|X_m|\ge|X_{m-1}|\ge\cdots\ge|X_0|.

Since ∣X0∣=1|X_0|=1 and ∣Xm∣≤m|X_m|\le m, not all of the inequalities ∣Xz∣≥∣Xz−1∣|X_z|\ge|X_{z-1}| can be strict, so for some zz, ∣Xz∣=∣Xz−1∣|X_z|=|X_{z-1}|, which means the projection from Zqz\mathbb{Z}_{q_z} to Zqz−1\mathbb{Z}_{q_{z-1}} is injective on XzX_z and hence

ρz(x)=∑j=1mλj∗ϕz,cj(ρz(xj))∈Ez,\rho_z(x)=\sum_{j=1}^{m}\lambda_j^*\phi_{z,c_j}(\rho_z(x_j))\in E_z,

where the equality follows from the compatibility of ϕr,c\phi_{r,c} with the projections πr\pi_r.

Thus xx lies in ρz−1(Ez)\rho_z^{-1}(E_z), which is of size ∣ρz−1(Ez)∣=∣Ez∣qqz<ϵqm|\rho_z^{-1}(E_z)|=|E_z|\frac{q}{q_z}<\frac{\epsilon q}{m}.

Every element of Λ∗⋅A\Lambda^*\cdot A lies in one of these mm sets, so a simple union bound gives that

∣Λ∗⋅A∣<ϵq.|\Lambda^*\cdot A|<\epsilon q.

We now deduce Theorem 1.5.

Proof of Theorem 1.5. Suppose Λ1,…,Λk\Lambda_1,\ldots,\Lambda_k and Φ1,…,Φℓ\Phi_1,\ldots,\Phi_\ell are multisets of non-zero integers. If Λi\Lambda_i is empty then every Φj\Phi_j dominates Λi\Lambda_i, and taking c>1c>1 means there are no sets AA with Λi⋅A=Zm\Lambda_i\cdot A=\mathbb{Z}_m.

If Φj\Phi_j dominates non-empty Λi\Lambda_i, then its domination scalar is rational; write it as r=a/br=a/b for integers a,ba,b. Then b⋅Φjb\cdot\Phi_j 1-dominates a⋅Λia\cdot\Lambda_i, and hence for every finite set AA, (b⋅Φj)⋅A(b\cdot\Phi_j)\cdot A contains a translate of (a⋅Λi)⋅A(a\cdot\Lambda_i)\cdot A.

If Λi⋅A=Zm\Lambda_i\cdot A=\mathbb{Z}_m, then

∣Φj⋅A∣≥∣b⋅(Φj⋅A)∣≥∣aZm∣=mgcd⁡(m,∣a∣)≥m∣a∣.|\Phi_j\cdot A|\ge|b\cdot(\Phi_j\cdot A)|\ge|a\mathbb{Z}_m|=\frac{m}{\gcd(m,|a|)}\ge\frac{m}{|a|}.

Taking ϵ<1∣a∣\epsilon<\frac{1}{|a|} contradicts condition 2.

On the other hand, suppose that no Φj\Phi_j dominates any Λi\Lambda_i for 1≤i≤k1\le i\le k and 1≤j≤ℓ1\le j\le\ell, and fix ϵ>0\epsilon>0 and c>0c>0. Let m0m_0 be any prime greater than cc and greater than the absolute value of every element of each Λi\Lambda_i and set A0=Zm0A_0=\mathbb{Z}_{m_0}. Since every Λi\Lambda_i is non-empty and every one of its coefficients is invertible modulo m0m_0, we have Λi⋅A0=Zm0\Lambda_i\cdot A_0=\mathbb{Z}_{m_0}.

For 1≤t≤ℓ1\le t\le\ell, suppose inductively that we have found an integer mt−1>cm_{t-1}>c and a subset At−1A_{t-1} of Zmt−1\mathbb{Z}_{m_{t-1}} such that

Λi⋅At−1=Zmt−1(1≤i≤k)\Lambda_i\cdot A_{t-1}=\mathbb{Z}_{m_{t-1}}\qquad(1\le i\le k)

and

∣Φj⋅At−1∣<ϵmt−1(1≤j<t).|\Phi_j\cdot A_{t-1}|<\epsilon m_{t-1}\qquad(1\le j<t).

Then apply Lemma 1.4 with Λ∗=Φt\Lambda^*=\Phi_t, with error ϵ\epsilon and with N=mt−1N=m_{t-1} to get a positive integer qq and a subset AA of Zq\mathbb{Z}_q such that:

  • qq is coprime to mt−1m_{t-1},

  • for all 1≤i≤k1 \le i \le k, Λi⋅A=Zq\Lambda_i \cdot A = \mathbb{Z}_q,

  • ∣Φt⋅A∣<ϵq|\Phi_t \cdot A| < \epsilon q.

Set mt=qmt−1>cm_t = qm_{t-1} > c and AtA_t to be the image of At−1×AA_{t-1} \times A under the Chinese Remainder Theorem isomorphism Zmt−1×Zq≅Zmt\mathbb{Z}_{m_{t-1}} \times\mathbb{Z}_q \cong\mathbb{Z}_{m_t}.

For any multiset Λ\Lambda, Λ⋅At≅(Λ⋅At−1)×(Λ⋅A)\Lambda\cdot A_t \cong(\Lambda\cdot A_{t-1}) \times(\Lambda\cdot A), ∣Λ⋅A∣≤q|\Lambda\cdot A| \le q and ∣Λ⋅At−1∣≤mt−1|\Lambda\cdot A_{t-1}| \le m_{t-1}, so it follows that

Λi⋅At=Zmt(1≤i≤k) and\Lambda_i \cdot A_t = \mathbb{Z}_{m_t} \quad(1 \le i \le k) \text{ and}
∣Φj⋅At∣=∣Φj⋅At−1∣∣Φj⋅A∣<(ϵmt−1)q=ϵmt(1≤j<t) and|\Phi_j \cdot A_t| = |\Phi_j \cdot A_{t-1}||\Phi_j \cdot A| < (\epsilon m_{t-1})q = \epsilon m_t \quad(1 \le j < t) \text{ and}
∣Φt⋅At∣=∣Φt⋅At−1∣∣Φt⋅A∣<mt−1(ϵq)=ϵmt|\Phi_t \cdot A_t| = |\Phi_t \cdot A_{t-1}||\Phi_t \cdot A| < m_{t-1}(\epsilon q) = \epsilon m_t

so the induction is complete.

Set m=mℓm = m_\ell and A=AℓA = A_\ell. Then m>cm > c and A⊆ZmA \subseteq\mathbb{Z}_m satisfies

Λi⋅A=Zm(1≤i≤k) and\Lambda_i \cdot A = \mathbb{Z}_m \quad(1 \le i \le k) \text{ and}
∣Φj⋅A∣<ϵm(1≤j≤ℓ).|\Phi_j \cdot A| < \epsilon m \quad(1 \le j \le\ell).

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\Lambda_1, \ldots, \Lambda_k are multisets of non-zero integers and suppose that for no i<ji < j does Λj\Lambda_j dominate Λi\Lambda_i.

Then for all positive reals ϵ\epsilon, there exists a positive integer qq and a subset AA of Zq\mathbb{Z}_q such that for all 1≤i<k1 \le i < k, ∣Λi+1⋅A∣<ϵ∣Λi⋅A∣|\Lambda_{i+1} \cdot A| < \epsilon|\Lambda_i \cdot A|.

Proof. If k=1k = 1, set q=1q = 1 and A=Z1A = \mathbb{Z}_1 and both conditions are vacuous. Suppose k≥2k \ge2.

By Lemma 1.4 with N=1N = 1 and error ϵ\epsilon applied to Λ1\Lambda_1 and Λ∗=Λ2\Lambda^* = \Lambda_2, there exists a positive integer q1q_1 and a subset A1A_1 of Zq1\mathbb{Z}_{q_1} such that Λ1⋅A1=Zq1\Lambda_1 \cdot A_1 = \mathbb{Z}_{q_1} and ∣Λ2⋅A1∣<ϵq1|\Lambda_2 \cdot A_1| < \epsilon q_1.

Suppose inductively for 2≤t<k2 \le t < k we have found a positive integer qt−1q_{t-1} and a subset At−1A_{t-1} of Zqt−1\mathbb{Z}_{q_{t-1}} such that for all 1≤j<t1 \le j < t,

∣Λj+1⋅At−1∣<ϵ∣Λj⋅At−1∣.|\Lambda_{j+1} \cdot A_{t-1}| < \epsilon|\Lambda_j \cdot A_{t-1}|.

Choose ϵt\epsilon_t such that ϵt∣Λt+1⋅At−1∣<ϵ∣Λt⋅At−1∣\epsilon_t|\Lambda_{t+1} \cdot A_{t-1}| < \epsilon|\Lambda_t \cdot A_{t-1}|. Apply Lemma 1.4 with targets Λ1,…,Λt\Lambda_1, \ldots, \Lambda_t, exceptional multiset Λt+1\Lambda_{t+1}, N=qt−1N = q_{t-1} and error ϵt\epsilon_t. Then there exists a positive integer qq coprime to qt−1q_{t-1} and a subset AA of Zq\mathbb{Z}_q such that Λj⋅A=Zq\Lambda_j \cdot A = \mathbb{Z}_q for all 1≤j≤t1 \le j \le t and ∣Λt+1⋅A∣<ϵtq|\Lambda_{t+1} \cdot A| < \epsilon_t q.

Then set qt=qqt−1q_t = qq_{t-1} and let AtA_t be the image of A×At−1A \times A_{t-1} under the Chinese Remainder Theorem isomorphism Zq×Zqt−1≅Zqt\mathbb{Z}_q \times\mathbb{Z}_{q_{t-1}} \cong\mathbb{Z}_{q_t}. Then for all 1≤j<t1 \le j < t,

∣Λj+1⋅At∣=∣Λj+1⋅At−1∣∣Λj+1⋅A∣=q∣Λj+1⋅At−1∣<qϵ∣Λj⋅At−1∣=ϵ∣Λj⋅At∣.|\Lambda_{j+1} \cdot A_t| = |\Lambda_{j+1} \cdot A_{t-1}||\Lambda_{j+1} \cdot A| = q|\Lambda_{j+1} \cdot A_{t-1}| < q\epsilon|\Lambda_j \cdot A_{t-1}| = \epsilon|\Lambda_j \cdot A_t|.

Further,

∣Λt+1⋅At∣=∣Λt+1⋅At−1∣∣Λt+1⋅A∣<qϵt∣Λt+1⋅At−1∣<qϵ∣Λt⋅At−1∣=ϵ∣Λt⋅At∣.|\Lambda_{t+1} \cdot A_t| = |\Lambda_{t+1} \cdot A_{t-1}||\Lambda_{t+1} \cdot A| < q\epsilon_t|\Lambda_{t+1} \cdot A_{t-1}| < q\epsilon|\Lambda_t \cdot A_{t-1}| = \epsilon|\Lambda_t \cdot A_t|.

Taking q=qk−1q = q_{k-1} and A=Ak−1A = A_{k-1} completes the proof.

Now we can deduce Theorem 1.2.

Proof of Theorem 1.2. Apply Corollary 3.1 to the multisets Λ1,…,Λk\Lambda_1,\ldots,\Lambda_k with an error value ϵ\epsilon we will specify later to get a subset AA of Zq\mathbb{Z}_q satisfying the required inequalities.

Let A∗A^* be the subset of the standard representatives {0,1,…,q−1}\{0,1,\ldots,q-1\} which is the preimage of AA under the canonical projection map.

Then it is clear that for every multiset Λ\Lambda of non-zero integers, Λ⋅A∗\Lambda\cdot A^* contains at least one preimage of each element of Λ⋅A\Lambda\cdot A, so ∣Λ⋅A∗∣≥∣Λ⋅A∣|\Lambda\cdot A^*| \ge|\Lambda\cdot A|.

Furthermore, if Λ={λ1,λ2,…,λh}\Lambda=\{\lambda_1,\lambda_2,\ldots,\lambda_h\} and we write wt⁡(Λ)=∣λ1∣+⋯+∣λh∣\operatorname{wt}(\Lambda)=|\lambda_1|+\cdots+|\lambda_h|, then one can show that (2wt⁡(Λ)+1)∣Λ⋅A∣≥∣Λ⋅A∗∣(2\operatorname{wt}(\Lambda)+1)|\Lambda\cdot A| \ge|\Lambda\cdot A^*|. If Λ\Lambda is empty, both ∣Λ⋅A∣|\Lambda\cdot A| and ∣Λ⋅A∗∣|\Lambda\cdot A^*| are equal to 1. Otherwise, it is clear that for any element a∈Λ⋅A∗a\in\Lambda\cdot A^*, ∣a∣<wt⁡(Λ)q|a|<\operatorname{wt}(\Lambda)q and hence there are at most 2wt⁡(Λ)2\operatorname{wt}(\Lambda) preimages of any given element of Λ⋅A\Lambda\cdot A.

Choose the error value ϵ\epsilon above, so that it is smaller than 12wt⁡(Λi)+1\frac{1}{2\operatorname{wt}(\Lambda_i)+1} for all 1≤i≤k1\le i\le k,

∣Λi+1⋅A∗∣≤(2wt⁡(Λi+1)+1)∣Λi+1⋅A∣<(2wt⁡(Λi+1)+1)ϵ∣Λi⋅A∣<∣Λi⋅A∣≤∣Λi⋅A∗∣|\Lambda_{i+1}\cdot A^*|\le(2\operatorname{wt}(\Lambda_{i+1})+1)|\Lambda_{i+1}\cdot A|<(2\operatorname{wt}(\Lambda_{i+1})+1)\epsilon|\Lambda_i\cdot A|<|\Lambda_i\cdot A|\le|\Lambda_i\cdot A^*|

as is required.

Multiple sets

In this section, we will use the multiset union operator ⊎\uplus. Given multisets Λ1\Lambda_1 and Λ2\Lambda_2, we denote the product

Λ1×Λ2=⨄j∈Λ1(j⋅Λ2).\Lambda_1\times\Lambda_2=\mathop{\biguplus}_{j\in\Lambda_1}(j\cdot\Lambda_2).

For example, {1,1,2}×{2,4}={2,2,4,4,4,8}\{1,1,2\}\times\{2,4\}=\{2,2,4,4,4,8\}.

Lemma 4.1. Suppose Λi,j\Lambda_{i,j} for 1≤i≤21\le i\le2 and 1≤j≤k1\le j\le k are multisets of at most tt non-zero integers, each of which has absolute value at most pp.

Fix an integer N≥2tp+1N\ge2tp+1 and for 1≤i≤21\le i\le2 define the multisets

Φi:=⨄j=1k(Λi,j×{N2kj,N(2k+1)j}).\Phi_i:=\mathop{\biguplus}_{j=1}^{k}\left(\Lambda_{i,j}\times\{N^{2kj},N^{(2k+1)j}\}\right).

For every non-zero real number rr, the following are equivalent:

  1. Φ1\Phi_1 rr-dominates Φ2\Phi_2

  1. Λ1,j\Lambda_{1,j} rr-dominates Λ2,j\Lambda_{2,j} for all jj.

Proof. Given a multiset SS, write σ(S):=∑s∈Ss\sigma(S):=\sum_{s\in S}s.

First note that every integer zz has at most one expression of the form z=∑i=0ℓaiNiz=\sum_{i=0}^{\ell}a_iN^i with integer coefficients of absolute value at most tptp and with non-zero leading coefficient: suppose we had two distinct such expressions z=∑i=0ℓ1aiNi=∑i=0ℓ2biNiz=\sum_{i=0}^{\ell_1}a_iN^i=\sum_{i=0}^{\ell_2}b_iN^i and let ii be the smallest index where ai≠bia_i\ne b_i (padding the shorter sequence with zeroes if necessary), then NN is a divisor of ai−bia_i-b_i, but 0<∣ai−bi∣≤2tp<N0<|a_i-b_i|\le2tp<N, which is impossible.

Now suppose we have submultisets S,TS,T of Φ1\Phi_1 with σ(S)=Nhσ(T)≠0\sigma(S)=N^h\sigma(T)\ne0 for some 1≤h≤k1\le h\le k. Let us write

S=⨄j=1k(N2kj⋅Sj,1⊎N(2k+1)j⋅Sj,2)S=\mathop{\biguplus}_{j=1}^{k}\left(N^{2kj}\cdot S_{j,1}\uplus N^{(2k+1)j}\cdot S_{j,2}\right)
T=⨄j=1k(N2kj⋅Tj,1⊎N(2k+1)j⋅Tj,2)T=\mathop{\biguplus}_{j=1}^{k}\left(N^{2kj}\cdot T_{j,1}\uplus N^{(2k+1)j}\cdot T_{j,2}\right)

where Sj,v,Tj,v⊆Λ1,jS_{j,v}, T_{j,v} \subseteq\Lambda_{1,j}. We can therefore write down two such expressions for σ(S)=Nhσ(T)\sigma(S) = N^{h}\sigma(T), namely:

σ(S)=∑j=1k(N2kjσ(Sj,1)+N(2k+1)jσ(Sj,2))\sigma(S) = \sum_{j=1}^{k}\left(N^{2kj}\sigma(S_{j,1}) + N^{(2k+1)j}\sigma(S_{j,2})\right)
Nhσ(T)=∑j=1k(N2kj+hσ(Tj,1)+N(2k+1)j+hσ(Tj,2)).N^{h}\sigma(T) = \sum_{j=1}^{k}\left(N^{2kj+h}\sigma(T_{j,1}) + N^{(2k+1)j+h}\sigma(T_{j,2})\right).

These two expressions must be the same. Because 1≤h≤k1 \le h \le k, the only exponent that appears in both expressions is (2k+1)h(2k+1)h. Indeed, writing E={2k,(2k+1)}×[k]E = \{2k,(2k+1)\} \times[k], one checks that E∩(E+h)={(2k+1)h}E \cap(E+h) = \{(2k+1)h\} for 1≤h≤k1 \le h \le k. Thus, after discarding any zero-sum layers, S=N(2k+1)h⋅Sh,2S = N^{(2k+1)h} \cdot S_{h,2} and T=N2kh⋅Th,1T = N^{2kh} \cdot T_{h,1} for some submultisets Sh,2,Th,1S_{h,2}, T_{h,1} of Λ1,h\Lambda_{1,h} with the same sum.

Now because Φ1\Phi_1 rr-dominates Φ2\Phi_2, there is a partition of some of the elements of Φ1\Phi_1 into non-empty disjoint submultisets, such that for each element λ\lambda of Φ2\Phi_2 there is a corresponding part whose elements sum to rλr\lambda.

Consider an element λ\lambda of Λ2,j\Lambda_{2,j}. There are corresponding elements λN2kj\lambda N^{2kj} and λN(2k+1)j\lambda N^{(2k+1)j} of Φ2\Phi_2. Thus there are corresponding parts of the domination partition TT and SS, summing to rλN2kjr\lambda N^{2kj} and rλN(2k+1)jr\lambda N^{(2k+1)j} respectively.

After applying the preceding observation with h=jh=j, the surviving low-layer portion has the form N2kjTj,1N^{2kj}T_{j,1} with σ(Tj,1)=rλ\sigma(T_{j,1}) = r\lambda. These Tj,1T_{j,1} remain disjoint as the occurrences of λ\lambda vary, because the original domination blocks were disjoint. Hence they witness that Λ1,j\Lambda_{1,j} rr-dominates Λ2,j\Lambda_{2,j}.

Conversely, if every Λ1,j\Lambda_{1,j} rr-dominates Λ2,j\Lambda_{2,j}, scale the witnessing blocks by N2kjN^{2kj} and N(2k+1)jN^{(2k+1)j}. The resulting blocks are disjoint across layers and witness that Φ1\Phi_1 rr-dominates Φ2\Phi_2. □\square

This allows us to determine exactly which inequalities of dilate sums of multiple sets can hold.

Proof of Theorem 1.3. Choose positive integers tt and pp such that every Λi,j\Lambda_{i,j} has at most tt elements, each of absolute value at most pp. Then if we set N=2tp+1N = 2tp + 1, Lemma 4.1 tells us that if we define

Φi=⨄j=1ℓ(Λi,j×{N2ℓj,N(2ℓ+1)j})\Phi_i = \mathbin{\biguplus}_{j=1}^{\ell}\left(\Lambda_{i,j} \times\{N^{2\ell j}, N^{(2\ell+1)j}\}\right)

for 1≤i≤k1 \le i \le k, then the condition in the statement of the theorem implies that for no i1<i2i_1 < i_2 does Φi2\Phi_{i_2} dominate Φi1\Phi_{i_1}.

Then Theorem 1.2 implies the existence of a finite set AA such that ∣Φi⋅A∣>∣Φi+1⋅A∣\lvert\Phi_i \cdot A\rvert> \lvert\Phi_{i+1} \cdot A\rvert for all 1≤i<k1 \le i < k. For 1≤j≤ℓ1 \le j \le\ell, set

Aj={N2ℓj,N(2ℓ+1)j}⋅A.A_j = \{N^{2\ell j}, N^{(2\ell+1)j}\} \cdot A.

Then, for every 1≤i≤k1 \le i \le k,

Φi⋅A=Λi,1⋅A1+Λi,2⋅A2+⋯+Λi,ℓ⋅Aℓ.\Phi_i \cdot A = \Lambda_{i,1} \cdot A_1 + \Lambda_{i,2} \cdot A_2 + \cdots+ \Lambda_{i,\ell} \cdot A_\ell.

The required inequalities for the Λi,j\Lambda_{i,j} now follow from the inequalities for the Φi\Phi_i. □\square

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 hh and multiset Λ\Lambda, let us write

h⊙Λ:=⨄u=1hΛ,h \odot\Lambda:= \mathbin{\biguplus}_{u=1}^{h}\Lambda,

where the union is empty when h=0h = 0.

In particular, h⊙{1}h \odot\{1\} is the multiset containing hh copies of 11. Note that h1⊙{1}h_1 \odot\{1\} dominates h2⊙{1}h_2 \odot\{1\} if and only if h1≥h2h_1 \ge h_2. Note also that for any finite set AA, hA=(h⊙{1})⋅AhA = (h \odot\{1\}) \cdot A.

Corollary 5.1. Suppose that (s1,t1),…,(sH2,tH2)(s_1,t_1),\ldots,(s_{H^2},t_{H^2}) is an ordering of the ordered pairs (s,t)(s,t) with 0≤s,t≤H−10 \le s,t \le H-1 in which (s,t)(s,t) always occurs after (s+1,t)(s+1,t) (assuming s<H−1s < H-1) and (s,t+1)(s,t+1) (assuming t<H−1t < H-1).

There exist finite sets A,B⊆ZA,B \subseteq\mathbb{Z} such that

∣s1A+t1B∣>∣s2A+t2B∣>…>∣sH2A+tH2B∣.|s_1A+t_1B| > |s_2A+t_2B| > \ldots> |s_{H^2}A+t_{H^2}B|.

Proof. For 1≤i≤H21 \le i \le H^2, let Λi,1=si⊙{1}\Lambda_{i,1} = s_i \odot\{1\} and Λi,2=ti⊙{1}\Lambda_{i,2} = t_i \odot\{1\}. Then by the definition of the ordering (si,ti)(s_i,t_i), if i<ji < j, at least one of sj<sis_j < s_i or tj<tit_j < t_i must hold. Hence for some v∈{1,2}v \in\{1,2\}, Λj,v\Lambda_{j,v} does not dominate Λi,v\Lambda_{i,v}.

Thus by Theorem 1.3, there exist finite sets A1,A2A_1,A_2 such that for all 1≤i<H21 \le i < H^2, ∣(si⊙{1})⋅A1+(ti⊙{1})⋅A2∣>∣(si+1⊙{1})⋅A1+(ti+1⊙{1})⋅A2∣|(s_i \odot\{1\}) \cdot A_1 + (t_i \odot\{1\}) \cdot A_2| > |(s_{i+1} \odot\{1\}) \cdot A_1 + (t_{i+1} \odot\{1\}) \cdot A_2|.

Setting A=A1A = A_1 and B=A2B = A_2, this can be rewritten as

∣s1A+t1B∣>∣s2A+t2B∣>…>∣sH2A+tH2B∣.|s_1A+t_1B| > |s_2A+t_2B| > \ldots> |s_{H^2}A+t_{H^2}B|.

Corollary 5.2. Suppose that (s1,t1),…,(sH(H+1)/2,tH(H+1)/2)(s_1,t_1),\ldots,(s_{H(H+1)/2},t_{H(H+1)/2}) is an ordering of the ordered pairs (s,t)(s,t) with 0≤t≤s≤H−10 \le t \le s \le H-1 in which (s,t)(s,t) occurs after (s+1,t)(s+1,t) (if s<H−1s < H-1) and after (s,t+1)(s,t+1) (if s>ts > t).

There exists a finite set A⊆ZA \subseteq\mathbb{Z} such that

∣s1A−t1A∣>∣s2A−t2A∣>…>∣sH(H+1)/2A−tH(H+1)/2A∣.|s_1A-t_1A| > |s_2A-t_2A| > \ldots> |s_{H(H+1)/2}A-t_{H(H+1)/2}A|.

Proof. For 1≤i≤H(H+1)/21 \le i \le H(H+1)/2, let Λi=(si⊙{1})⊎(ti⊙{−1})\Lambda_i = (s_i \odot\{1\}) \uplus(t_i \odot\{-1\}).

If Λi\Lambda_i rr-dominates Λj\Lambda_j for some non-zero real number rr then there exists a way of partitioning some of the elements of Λi\Lambda_i into parts that sum to rr times the elements of Λj\Lambda_j. We will show that i≤ji \le j.

If Λj\Lambda_j is empty, then j=H(H+1)/2j = H(H+1)/2 and hence i≤ji \le j. We may therefore suppose that Λj\Lambda_j is non-empty. Then the parts sum to either rr or −r-r and hence rr is a non-zero integer.

Counting the copies of 11 and −1-1 in the blocks, if r>0r > 0, then si≥rsj≥sjs_i \ge rs_j \ge s_j and ti≥rtj≥tjt_i \ge rt_j \ge t_j, so i≤ji \le j. If r<0r < 0, then si≥∣r∣tj≥tjs_i \ge|r|t_j \ge t_j and ti≥∣r∣sj≥sjt_i \ge|r|s_j \ge s_j. Since si≥tis_i \ge t_i and sj≥tjs_j \ge t_j, this again gives si≥ti≥sjs_i \ge t_i \ge s_j and ti≥sj≥tjt_i \ge s_j \ge t_j, so i≤ji \le j.

Thus no Λi\Lambda_i dominates Λj\Lambda_j with j<ij < i and Theorem 1.2 gives the existence of such an AA.

Corollary 5.3. Suppose that (s1,t1),…,(sn,tn)(s_1,t_1),\ldots,(s_n,t_n) are integer vectors with non-zero coordinates such that for all i≠ji \ne j, (si,ti)(s_i,t_i) is not parallel to either (sj,tj)(s_j,t_j) or (tj,sj)(t_j,s_j).

Then there exists a finite set A⊆ZA \subseteq\mathbb{Z} such that

∣s1⋅A+t1⋅A∣>∣s2⋅A+t2⋅A∣>…>∣sn⋅A+tn⋅A∣.|s_1 \cdot A+t_1 \cdot A| > |s_2 \cdot A+t_2 \cdot A| > \ldots> |s_n \cdot A+t_n \cdot A|.

Proof. For 1≤i≤n1 \le i \le n, let Λi={si,ti}\Lambda_i = \{s_i,t_i\}.

If Λi\Lambda_i rr-dominates Λj\Lambda_j, there is a way of partitioning some of the elements of Λi\Lambda_i into blocks that sum to rr times the elements of Λj\Lambda_j. Since each block will need a non-zero sum, both blocks must be non-empty. Then, since Λi\Lambda_i and Λj\Lambda_j are the same size, each block is a singleton.

So either (si,ti)=r(sj,tj)(s_i,t_i) = r(s_j,t_j) or (si,ti)=r(tj,sj)(s_i,t_i) = r(t_j,s_j). Since (si,ti)(s_i,t_i) is not parallel to either (sj,tj)(s_j,t_j) or (tj,sj)(t_j,s_j) when i≠ji \ne j, it follows that i=ji = j.

Thus no Λi\Lambda_i dominates any Λj\Lambda_j with j<ij < i and Theorem 1.2 gives the existence of such an AA.

AI

The author used ChatGPT for a literature search and Codex for proofreading.

References

  1. [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. [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

Paper details

vlnc:W_vwgpmy6p
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents