ON A QUESTION OF ALON DANIEL ALTMAN Abstract. A system of linear equations in Fn

2025-05-02 0 0 363.74KB 12 页 10玖币

侵权投诉

ON A QUESTION OF ALON

DANIEL ALTMAN

Abstract. A system of linear equations in Fn

pis common if every two-colouring

of Fn

pyields at least as many monochromatic solutions as a random two-colouring,

asymptotically as n→ ∞. By analogy to the graph-theoretic setting, Alon has asked

whether any (non-Sidorenko) system of linear equations can be made uncommon by

adding suﬃciently many free variables. Fox, Pham and Zhao answered this question

in the aﬃrmative among systems which consist of a single equation. We answer Alon’s

question in the negative.

We also observe that the property of remaining common despite that addition of

arbitrarily many free variables is closely related to a notion of commonness in which

one replaces the arithmetic mean of the number of monochromatic solutions with the

geometric mean, and furthermore resolve questions of Kamˇcev–Liebenau–Morrison.

1. Introduction

In graph theory, a graph His called common if every two-colouring of Kncontains

at least at many monochromatic copies of Has a random two-colouring does (in the

limit n→ ∞). Goodman [Goo59] proved that K3is common. Erd˝os conjectured

that K4is common [Erd62] and subsequently Burr and Rosta conjectured [BR80] that

every graph is common. These conjectures were disproved by Sidorenko [Sid89] and

Thomason [Tho89] who demonstrated respectively that a triangle with a pendant edge

and K4are in fact not common. The classiﬁcation of common graphs remains very much

open to this day.

One observes that if Hsatisﬁes the stronger property that for every large graph G,

among all subsets of Gof ﬁxed density, a random subset of Gcontains the fewest copies

of H(in the limit |V(G)|→∞), then His certainly common. Graphs satisfying this

stronger property are called Sidorenko. Conjecturally [Sid93], all bipartite graphs are

Sidorenko; this conjecture remains wide open (despite the resolution of various special

cases). Certainly, since Sidorenko’s conjecture is not known to be false, all known

instances of uncommon graphs are not bipartite. In fact, every non-bipartite graph can

be made uncommon by the addition of suﬃciently many pendant edges (an edge eis

pendant to a graph Hif |e∩V(H)|= 1).

Theorem 1.1 ( [JST96]).If His a non-bipartite graph with m≥3vertices, then there

is a positive integer l0(m)such that any graph obtained by successively adding at least

l0pendant edges to His uncommon.

arXiv:2210.13515v2 [math.CO] 28 Oct 2022

2 DANIEL ALTMAN

Alon has asked whether the analogous result is true in the arithmetic setting. A

system of linear equations in Fn

pis common if every two-colouring of Fn

pyields at least as

many monochromatic solutions as a random two-colouring, asymptotically as n→ ∞. A

system of linear equations in Fn

pis Sidorenko if among all subsets Sof Fn

pof ﬁxed density,

the number of solutions in Sis minimised when Sis a random set, asymptotically as

n→ ∞. It is clear that if a linear system is Sidorenko, then it is common. Saad and Wolf

initiated the study of these properties in the arithmetic setting [SW17]. For both the

Sidorenko and common properties, necessary [FPZ21] and suﬃcient [SW17] conditions

for systems containing a single equation are known (in fact, a single equation in an even

number of variables is Sidorenko if and only if it is common, and an equation in an

odd number of variables is necessarily common but not Sidorenko). The classiﬁcation

problems for systems containing more than one equation remain wide open, despite

recent interest and the resolution of special cases; see [FPZ21], [KLM21a], [KLM21b],

[Ver21a], [Ver21b].

It transpires that adding a free variable to a system of linear equations (equivalently,

a free dimension to the solution space) corresponds to the addition of a pendant edge

in the graph-theoretic setting. In those cases when one can transfer between the graph-

theoretic and arithmetic settings via Cayley graph constructions, these operations are

equivalent. See [SW17, Example 4.2] for an instance of this correspondence and else-

where in that paper for a brief discussion of the correspondence in general. For l≥0,

let Ψ(l)be the linear system attained by adding lfree variables to Ψ.

Question 1.2 (Alon, [SW17, Question 4.1]).Is it true that for all non-Sidorenko Ψ,

there exists l0such that for all l≥l0we have Ψ(l)is uncommon?

For example, it is known that three term arithmetic progressions, whose solution

space is parameterised Ψ = (x, x +d, x + 2d), are common. Is it true that the system

given by Ψ(l)= (x, x +d, x + 2d, y1, . . . , yl) is uncommon for all lsuﬃciently large? The

answer is yes by the following theorem of Fox–Pham–Zhao.

Theorem 1.3 ( [FPZ21, Theorem 1.5]).The answer to Question 1.2 is yes among all

Ψwhose image has codimension one.

In light of Question 1.2 and for convenience in this document, we will refer to systems

Ψ with the property that Ψ(l)is common for all suﬃciently large las Alon. We have

mentioned already that Sidorenko implies common; in fact it is not diﬃcult to see that

Sidorenko implies Alon. In this language, the above question essentially (i.e. under the

assumption that linear systems cannot oscillate inﬁnitely often between common and

uncommon under the addition of free variables) asks whether Sidorenko is equivalent to

Alon. This is true in the graph-theoretic setting under Sidorenko’s conjecture. It turns

out that it is not true in the arithmetic setting.

Theorem 1.4. There is a system of linear equations which is Alon but not Sidorenko,

so the answer to Question 1.2 is no.

ON A QUESTION OF ALON 3

The example which demonstrates the negative answer to Question 1.2 is the following

rank 2 system of equations in 9 variables:

x1−x2+x3−x4= 0

x5−x6+x7−x8+x9= 0.

Theorem 1.4 is proven in Section 3. As an intermediate lemma in the proof, we provide

a lower bound on the geometric mean of the number of monochromatic solutions to Φ.

We show in Section 4 that a lower bound of this type is in fact also necessary, and

indeed that a slightly weaker version of the Alon property is equivalent to a geometric

notion of commonness in which one asks that the geometric mean of the number of

monochromatic solutions is at least that of a random two-colouring. This is proven in

Proposition 4.5. The intended utility is that geometric commonness is oftentimes more

easily studied than the Alon property.

It transpires that Φ also exhibits a negative answer to a question of Kamˇcev–Liebenau–

Morrison. Recall that a system is said to be translation-invariant if it is solved by setting

x1=x2=x3=···. If a system is not translation invariant, then the set of elements of

pwhose ﬁrst entry is equal to one has positive density but no solutions, so any system

which is not translation-invariant cannot be Sidorenko. The only known examples of

systems which are not translation invariant and are common are systems of rank one

(i.e. systems comprising a single equation), whereupon commonness follows trivially

from a cancellation which does not occur for systems of two or more equations. This

inspired the following question of Kamˇcev–Liebenau–Morrison.

Question 1.5. [KLM21b, Question 5.6] Does there exist a system of rank at least two

which is common, but not translation-invariant?

Theorem 1.6. The answer to Question 1.5 is yes.

The system Φ has rank two and is not translation invariant. The proof of Theo-

rem 1.6 is completed in Lemma 3.1, which shows that Φ is common. Since upload-

ing this document to the arXiv, the author has been made aware that Question 1.5

has been independently resolved in Fn

2by Kr´al’–Lamaison–Pach in forthcoming work.

See [KLP22].

Finally, we also take this opportunity to address the following question of Kamˇcev–

Liebenau–Morrison.

Question 1.7. [KLM21a, Question 6.3] Suppose that Ψis a linear system such that

there is a set A⊂Fn

psuch that the density of monochromatic solutions in (A, Ac)is less

than αt+ (1 −α)t, where α=|A|/pn. Is Ψnecessarily uncommon if one restricts one’s

attention to sets of density roughly 1/2?

For a suitable interpretation of ‘roughly’, the answer to [KLM21a, Question 6.3] is no,

even with the stronger demand that the density of monochromatic solutions in (A, Ac)

is less than 21−t. To see why, we will need to introduce some notation.

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

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

10 玖币 0人已下载

立即下载

摘要：

ONAQUESTIONOFALONDANIELALTMANAbstract.AsystemoflinearequationsinFnpiscommonifeverytwo-colouringofFnpyieldsatleastasmanymonochromaticsolutionsasarandomtwo-colouring,asymptoticallyasn!1.Byanalogytothegraph-theoreticsetting,Alonhasaskedwhetherany(non-Sidorenko)systemoflinearequationscanbemadeuncommonby...

展开>> 收起<<

ON A QUESTION OF ALON DANIEL ALTMAN Abstract. A system of linear equations in Fn.pdf

共12页,预览3页

还剩页未读，继续阅读

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

ON A QUESTION OF ALON DANIEL ALTMAN Abstract. A system of linear equations in Fn

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: