THE POPULARITY GAP VSEVOLOD F. LEV AND ILYA D. SHKREDOV Abstract. Suppose that Ais a nite nonempty subset of a cyclic group of either

2025-05-06 1 0 383.97KB 16 页 10玖币

侵权投诉

THE POPULARITY GAP

VSEVOLOD F. LEV AND ILYA D. SHKREDOV

Abstract. Suppose that Ais a ﬁnite, nonempty subset of a cyclic group of either

inﬁnite or prime order. We show that if the diﬀerence set A−Ais “not too large”,

then there is a nonzero group element with at least as many as (2 + o(1))|A|2/|A−A|

representations as a diﬀerence of two elements of A; that is, the second largest number of

representations is, essentially, twice the average. Here the coeﬃcient 2 is best possible.

We also prove continuous and multidimensional versions of this result, and obtain

similar results for suﬃciently dense subsets of an arbitrary abelian group.

1. Background and summary of results

A large body of problems, conjectures, and results in additive combinatorics assert, in

diﬀerent ways, that, normally, the number-of-representations function exhibits an irreg-

ular behaviour. The general framework for this line of research is as follows.

For ﬁnite subsets Aand Band an element gof an abelian group, let rA,B(g) :=

|A∩(g−B)|; that is, rA,B (g) is the number of representations of gas a sum of an

element of Aand an element of B. How close to a constant function can the function

rA,B be?

In this paper we consider representations by diﬀerences; that is, we are concerned with

the special case where B=−A. Notation-wise, we abbreviate rA,−Aas rA.

Clearly, the largest value attained by the function rAis |A|. Our principal results

show that for the cyclic groups of either inﬁnite or prime order, the second largest value

attained by rAis, essentially, at least twice the average value.

For a prime p, by Cpwe denote the cyclic group of order p.

Theorem 1. Suppose that pis a prime, A⊆Cpis a nonempty subset, and δ∈(0,1/3).

|A−A| ≤ min{K|A|,2(p+ 1)/3}, K < |A|δ,

then there is a nonzero element d∈Cpsuch that rA(d)>2K−1|A|(1 −2δln(2/δ)).

The following integer analog of Theorem 1 is, in fact, its immediate consequence.

Theorem 2. Suppose that Ais a ﬁnite, nonempty set of integers, and that δ∈(0,1/3).

|A−A| ≤ K|A|, K < |A|δ,

then there is an integer d6= 0 such that rA(d)>2K−1|A|(1 −2δln(2/δ)).

arXiv:2210.09614v1 [math.NT] 18 Oct 2022

2 VSEVOLOD F. LEV AND ILYA D. SHKREDOV

Comparing Theorems 1 and 2, we see that the bounds obtained are not aﬀected by

the “modulo-poverlapping”. Loosely speaking, there is no diﬀerence between the group

Cpand the group of integers Zas far as the second largest value of the function rAis

concerned.

The following theorem establishes a similar estimate in terms of the length of the set

Ainstead of the size of its diﬀerence set.

Theorem 3. Suppose that L > 1, and that A⊆[1, L]is a nonempty set of integers. If

|A−A|<|A|1+δwith δ∈(0,1/3), then there is an integer d6= 0 such that rA(d)>

|A|2

L(1 −2δln(2/δ)).

We note that the assumption |A−A|<|A|1+δof Theorem 3 holds trivially if Ais

suﬃciently dense in [1, L]; say, |A|>(2L)1/(1+δ)suﬃces.

Theorem 3 follows readily from Theorem 2 by letting K:= |A−A|/|A|and observing

that then 2K−1|A|= 2|A|2/|A−A|>|A|2/L.

Apart from the factor 1 −2δln(2/δ), the lower bounds obtained in Theorems 1–3 are,

essentially, best possible; they are attained, for example, when Ais an interval or an

appropriately sampled random set.

Interestingly, Theorems 1–3 cannot be obtained by a straightforward averaging as the

number of elements d∈A−Awith rA(d) large can have “zero measure”.

Claim 1. For any ε∈(0,1) there is a ﬁnite, nonempty set A⊂Zsuch that

nd:rA(d)≥(1 −ε)2|A|2

|A−A|o≤2ε|A−A|.

Since the function rA:d7→ |A∩(A+d)|is generalized by the functions (d1, . . . , dk−1)7→

|A∩(A+d1)∩···∩(A+dk−1)|(see the next section), it is natural to extend Theorem 1

onto the intersection of k≥3 translates of the set A. In this direction, we prove the

following multidimensional generalization.

Theorem 4. Suppose that pis a prime, A⊆Cpis a nonempty subset, and δ∈(0,1/(3k))

with an integer k≥3. If

|A−A| ≤ min{K|A|,2(p+ 1)/3}, K < |A|δ,

then there are pairwise distinct, nonzero elements d1, . . . , dk−1∈Cpsuch that

|A∩(A+d1)∩ ··· ∩ (A+dk−1)|>2k−1K−(k−1)|A|(1 −3δk2ln(1/kδ)).

From Theorem 4 one can easily derive multidimensional analogs of Theorems 2 and 3;

we omit the details.

Our next result exhibits irregularities in the behaviour of the function rAfor large

subsets Aof an arbitrary ﬁnite abelian group.

THE POPULARITY GAP 3

Theorem 5. Suppose that Ais a subset of a ﬁnite abelian group Gsuch that |A| ≥ 210

and |A−A|= (1 −ε)|G|with 0< ε ≤2−5. If |A−A|≤|A|1+√ε/2, then there is a

nonzero element d∈Gsuch that rA(d)≥|A|2

|A−A|1 + 1

8√ε.

Finally, we prove a continuous analog of Theorem 3. For a function f∈L1(R), let

(f◦f)(x) := ZR

f(t)f(x+t)dt.

Theorem 6. Suppose that fis a real, nonnegative function with supp(f)⊆[0,1]. If fis

not constant on its support then, letting ρ:= kfk2/kfk1, for any 0< δ ≤min{1

2ρ12 ,1

28}

we have

sup

x∈[−1,1]\[−δ,δ]

(f◦f)(x)

kfk2

1≥1−8 max n8

√2δ, ln logρ(1/2δ)

logρ(1/2δ)o.

We note that the matching upper bound kf◦fk∞≤ kfk2

1is trivial.

The quantity logρ(1/2δ) characterizes the length of the forbidden interval [−δ, δ] as

measured against the “scatter” of f. If logρ(1/2δ) is small enough, then we can have

supp(f)⊆[0, δ]; in this case supp(f◦f)⊆[−δ, δ] and there do not exist x /∈[−δ, δ] with

(f◦f)(x)>0. Theorem 6 assumes logρ(1/2δ)≥12, and the remainder term is o(1) in

the regime where logρ(1/2δ)→ ∞ and δ→0.

Our argument involves two major components: the higher energies technique [SS13]

and a result in the spirit of [L01] establishing an extremal property of the interval subsets

of prime-order groups. The central role is played by the following quantity.

For ﬁnite subsets Aand Dof an abelian group and integer k≥1, let T(k)

D(A) be the

number of k-tuples (a1, . . . , ak)∈Aksuch that ai−aj∈Dfor any 1 ≤i, j ≤k. In

particular, T(k)

D(D) is the number of k-tuples (d1, . . . , dk) such that

{0, d1, . . . , dk}−{0, d1, . . . , dk} ⊆ D.

The key result we prove about this quantity shows that in a group of prime order, if

0∈D= (−D), then T(k)

D(A) can only get larger if Aand Dare replaced with the

intervals A, D of sizes |A|=|A|and |D|=|D|, respectively, centered at 0; that is, either

A= [−m, m], or A= [−(m−1), m] with m=b|A|/2cin both cases, and similarly for

Proposition 1. For any prime p≥5, integer k≥1, and nonempty subsets A, D ⊆Cp

with 0∈D= (−D), we have

T(k)

D(A)≤T(k)

D(A),

where A, D ⊆Cpare intervals with |A|=|A|and |D|=|D|, centered at 0.

As a consequence of Proposition 1 we prove the following, slightly technical, corollary.

4 VSEVOLOD F. LEV AND ILYA D. SHKREDOV

Corollary 1. For any prime p≥5, integer k≥3, and subset D⊆Cpwith 0∈D=

(−D)and k≤ |D| ≤ 2

3(p+ 1), we have

T(k)

D(D)≤3k2−k−1|D|k.

We now turn to the proofs of the results discussed above. In the next section we intro-

duce the basic notation, collect auxiliary tools needed for the proofs, and prove Claim 1.

In Section 3 we prove the key Proposition 1. Theorem 1 is derived from Proposition 1 in

Section 4 where also Corollary 1 is proved; as we have noticed, Theorems 2 and 3 follow

from Theorem 1 and therefore do not require any additional consideration. Theorems 5

and 4 are proved in Sections 5 and 6, respectively. A proof of Theorem 6, along with

a somewhat broader context for the problems studied in this paper, is outlined in the

concluding Section 7.

2. Notation and preliminaries

In this section Aand Dare ﬁnite, nonempty subsets of an abelian group G.

Following [SS13] (but using a diﬀerent notation), for an integer k≥2 we let

R(k)

A(x1, . . . , xk−1) := |A∩(A+x1)∩ ··· ∩ (A+xk−1)|, x1, . . . , xk−1∈G. (1)

This quantity generalizes the function rAwhich is obtained as a particular case k= 2.

Alternatively, R(k)

A(x1, . . . , xk−1) is the number of representations of (x1, . . . , xk−1) as a

diﬀerence of an element of the “diagonal” {(a, . . . , a) : a∈A}and an element of the

Cartesian power Ak−1. Clearly,

x1,...,xk−1∈G

R(k)

A(x1, . . . , xk−1) = |A|k.(2)

Less obvious is the identity

x1,...,xk−1∈GR(k)

A(x1, . . . , xk−1)l=X

y1,...,yl−1∈GR(l)

A(y1, . . . , yl−1)k(3)

valid for any k, l ≥2 and any ﬁnite subset A⊆G, see [SV12, Lemma 2.8].

The common value of the two sums in (3) is denoted Ek,l(A); thus, Ek,l(A) = El,k(A).

We write

Ek(A) := Ek,2(A) = X

x∈G|A∩(A+x)|k.

Let µ(A) := max{rA(d): d∈A−A, d 6= 0}; that is, µ(A) is the second largest value

attained by the function rA. We have

Ek(A) = X

x∈G|A∩(A+x)|k≤ |A|k+ (µ(A))k−1|A|2.(4)

Recall that in Section 1 we have deﬁned

T(k)

D(A) := |{(a1, . . . , ak)∈Ak:ai−aj∈D, 1≤i, j ≤k}|, k ≥1.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

THEPOPULARITYGAPVSEVOLODF.LEVANDILYAD.SHKREDOVAbstract.SupposethatAisanite,nonemptysubsetofacyclicgroupofeitherinniteorprimeorder.WeshowthatifthedierencesetAAisottoolarge",thenthereisanonzerogroupelementwithatleastasmanyas(2+o(1))jAj2=jAAjrepresentationsasadierenceoftwoelementsofA;thatis,theseco...

展开>> 收起<<

THE POPULARITY GAP VSEVOLOD F. LEV AND ILYA D. SHKREDOV Abstract. Suppose that Ais a nite nonempty subset of a cyclic group of either.pdf

共16页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

THE POPULARITY GAP VSEVOLOD F. LEV AND ILYA D. SHKREDOV Abstract. Suppose that Ais a nite nonempty subset of a cyclic group of either

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: