-1
votes
0answers
23 views

Proof that $G(3)\le 7$ [migrated]

Let $G(k)$ be the minimal $n$ s.t. every sufficiently large integer is the sum of $n$ nonnegative $k$th powers. Does anybody know where I can find Vaughan's proof that $G(3)\le 7$? I can't find a ...
1
vote
1answer
249 views

Karolyi's theorem for finite groups and its extensions

Suppose that $\mathbb A = (A, +)$ is a (possibly non-commutative) group, and denote by $p(\mathbb A)$ the minimum of $|S|$ as $S$ ranges in the set of non-trivial subgroups of $\mathbb A$, with the ...
21
votes
2answers
986 views

The Erdős-Turán conjecture or the Erdős' conjecture?

This has been bothering me for a while, and I can't seem to find any definitive answer. The following conjecture is well known in additive combinatorics: Conjecture: If $A\subset \mathbb{N}$ ...
1
vote
1answer
151 views

Distribution of colors in the number of integer partitions of n

Given an integer $n$ the number of partitions of $n$ into two colors can be represented as $$p_2(n)=\sum_{k=0}^n p(k)p(n-k)$$ where $p(k)$ counts the number of ordinary partitions of $k.$ What is the ...
5
votes
1answer
398 views

Additive Combinatorics - reference request

Let $A$ be a finite set of integers with $|A \hat{+} A| \leq K|A|$, where the $\hat{+}$ denotes restricted sumset: the set of all $a_1 + a_2$ with $a_1, a_2 \in A$ and $a_1 \neq a_2$. Claim: $|A + ...
4
votes
2answers
566 views

How local the property of “being a partition” is?

Note: The problem is solved! See EDIT below. The following question about integer partitions arose from a purely "practical" question: Does there exist better dynamic programming algorithms for the ...
6
votes
1answer
333 views

Bounds on the size of sets not containing a given finite pattern

Recall the following version of Szemerédi's Theorem: let $r_k(N)$ be the largest cardinality of a subset of $[N]:=\{1,\ldots, N\}$ which does not contain an arithmetic progression of length $k$. Then, ...
12
votes
2answers
579 views

Arithmetic progressions modulo $p$ under the squaring map

I feel that the following problem should be known, but I'm not sure where to look for it. Fix a real constant $\frac{1}{2} \ge \epsilon > 0$. For varying primes $p$, Let $A_p$ denote the set of ...
11
votes
2answers
591 views

Sums of subsets of $\mathbb{Z}/n\mathbb{Z}$

I have encountered a problem that I suspect has been thoroughly studied but I have not been able to find references. Can anyone point me to a published reference dealing with this or a closely related ...
11
votes
2answers
692 views

Did Erdős publish his proof of the multiplicative version of the Erdős-Turán conjecture?

I read in an article of Erdős ("Extremal problems in number theory") that he had a proof of the multiplicative version of the Erdős-Turán conjecture. The statement of this theorem is Let $a_1 < ...
4
votes
1answer
289 views

Is the generalized Erdős–Heilbronn problem true for finite cyclic groups?

The generalized Erdős–Heilbronn (GEH) theorem, which is proved by da Silva and Hamidoune in 1994, states that: Theorem. If p is a prime and $X$ is a subset of $\mathbb{Z}_p$, then $|\hat{k}X| \geq ...
3
votes
1answer
988 views

Queries about the Skolem-Mahler-Lech theorem (integer zeros of exponential polynomials)

The Skolem-Mahler-Lech Theorem says that the integer zeros of an exponential polynomial are the union of complete arithmetic progressions and a finite number of exceptional zeros. ...
6
votes
1answer
803 views

Additive combinatorics and large Fourier coefficients

Elon Lindenstrauss explains in his talk at the MSRI in Fall 2008 (the relevant comment is at minute 41 of the video) that the set of large Fourier coefficients of a probability measure $\mu$ on the ...
4
votes
2answers
491 views

Sum of sets modulo a square

I would be glad to see a reference to the following easy lemma in additive combinatorics: if $A_1$ and $A_2$ are two sets of remainders modulo $n^2$, each has cardinality $n > 1$ and all elements ...
7
votes
1answer
431 views

A variation of Minkowski sum

I have to work with the following variation of Minkowski sum: Let $\mathbb E$ be a Euclidean space and $K$ be a convex set in $\mathbb E\times \mathbb E$. Set $$K^+=\{\\,x+y\in\mathbb ...