Adding Distinct Congruence Classes Modulo a Prime
Adding Distinct Congruence Classes Modulo a Prime
复制标题
DOI：
10.1080/00029890.1995.11990565
复制
发表时间：
1995-03
影响因子：
0.5
通讯作者：
N. Alon;M. Nathanson;I. Ruzsa
中科院分区：
文献类型：
--
作者：
N. Alon;M. Nathanson;I. Ruzsa
柯西-达文波特定理指出，如果A和B是模为素数p的同余类的非空集，且|A|=k且|B|=L，则和集A+B至少包含MIN(p，k+L−1)同余类。由此推论，求和集2A至少包含Min(p，2k−1)个同余类。őS和海尔布伦30年前猜想，至少有Min(p，2k−3)同余类可以写成A的两个不同元素的和。ErdőS在他的演讲和论文中经常提到这个问题(例如erdőS-Graham[4，p.95])。最近，Dias da Silva和Hamidoune[3]用线性代数和对称群的表示理论证明了这个猜想。本文仅利用多项式的最基本性质，给出了ErdőS-海尔布伦猜想的一个简单证明。该方法实际上是对ErdőS-海尔布伦猜想和柯西-达文波特定理的推广。
The Cauchy-Davenport theorem states that if A and B are nonempty sets of congruence classes modulo a prime p, and if |A| = k and |B| = l, then the sumset A + B contains at least min(p, k + l − 1) congruence classes. It follows that the sumset 2A contains at least min(p, 2k − 1) congruence classes. Erdős and Heilbronn conjectured 30 years ago that there are at least min(p, 2k − 3) congruence classes that can be written as the sum of two distinct elements of A. Erdős has frequently mentioned this problem in his lectures and papers (for example, Erdős-Graham [4, p. 95]). The conjecture was recently proven by Dias da Silva and Hamidoune [3], using linear algebra and the representation theory of the symmetric group. The purpose of this paper is to give a simple proof of the Erdős-Heilbronn conjecture that uses only the most elementary properties of polynomials. The method, in fact, yields generalizations of both the Erdős-Heilbronn conjecture and the Cauchy-Davenport theorem.