Questions on the subject additive combinatorics, also known as arithmetic combinatorics, such as questions on: additive bases, sum sets, inverse sum set theorems, sets with small doubling, Sidon sets, Szemerédi's theorem and its ramifications, Gowers uniformity norms, etc. Often combined with the ...

learn more… | top users | synonyms

49
votes
5answers
1k views

Is the set $ AA+A $ always at least as large as $ A+A $?

Let $A$ be a finite set of real numbers. Is it always the case that $|AA+A| \geq |A+A|$? My first instinct is that this is obviously true, and there is a one-line proof which I am foolishly ...
0
votes
0answers
47 views

On covering by smooth numbers

Denote $P(y)=\mathsf{greatest}\mbox{ }\mathsf{prime}\mbox{ }\mathsf{factor}\mbox{ }\mathsf{of}\mbox{ }y$. Denote $S(x,y)=\{n<x: P(n)<y\}$. Denote $S_t(x,y)=\sum_{i=1}^tS(x,y)$ as $t$-fold ...
11
votes
2answers
574 views

Sum and product estimate over integers, rationals, and reals

My question is the following: is finding a lower bound for $|A+A\cdot A|$ (as a function of $|A|$) where $A$ is any finite subset of the positive integers equivalent to finding the same lower bound ...
4
votes
2answers
150 views

Ordered lattice point enumeration

I initially asked this question over at StackOverflow as it has algorithmic flavor to it, but I haven't been getting much traction so I thought I would probe the mathematics community. Setup: Let ...
24
votes
3answers
490 views

Ordering subsets of the cyclic group to give distinct partial sums

Suppose that you are given a set $S$ of $k$ nonzero elements from $\mathbb{Z}_n$. Is it always possible to order the elements of $S$, say $a_1,a_2,\dots,a_k$ in such a way that the partial sums ...
3
votes
1answer
460 views

Coin problem with permutations

Let $a,b,c$ be positive integers with gcd$(a,b,c)=1$, and let $\mathbb{N}$ denote the set of nonnegative integers. It is well known that $\mathbb{N} \setminus (a \mathbb{N}+b \mathbb{N} + c ...
5
votes
1answer
178 views

Element with unique representation in A+B

Let $A, B \subseteq \mathbb{Z}$ be finite subsets of the integers. Then there exists an element in $A+B$ with a unique representation as a sum of an element in $A$ and an element in $B$, namely ...
2
votes
2answers
505 views

Asymptotic formula for the number of ways to write a number as the sum of $k$ triangular numbers

How would one derive an asymptotic formula for the number of representations of a number $n$ as the sum of $k$ numbers of the form $\frac{m(m + 1)}{2}$ I think that one could use the circle method, ...
2
votes
2answers
183 views

Applications of Szemeredi's Theorem

Szemeredi's Theorem is a famous theorem in Additive Combinatorics, Ergodic Theory and maybe some other parts of Mathemtaitcs: (Szemeredi's Theorem) Let $\Lambda \in \mathbb{Z}$ be a subset of ...
2
votes
0answers
37 views

How is the structure of spectrum in cap-sets with no strong increments unrealistic if density is too large?

I am reading this excellent paper by Bateman and Katz on improved bounds on the cap set problem. Let A be a set in $\mathbb{F}_3^n$ containing no 3-term arithmetic progression and let $A(x)$ denote ...
1
vote
1answer
98 views

Pollard's inequality modulo a composite number

Here is question similar to another one asked today (Proof of Pollard's inequality). When working in $\mathbb{Z}/n\mathbb{Z}$ for composite $n$ Cauchy-Davenport and Pollard's inequalities may not ...
2
votes
2answers
158 views

Proof of Pollard's inequality

Let $A, B \subseteq \mathbb{Z}_p$, $p$ prime, $|B| \leq |A|$. If $N_t$ denotes the number of elements of $\mathbb{Z}_p$ having at least $t$ representations as $a+b$, $a \in A, b \in B$, Pollard's ...
2
votes
1answer
96 views

On a problem about $GF(2)^n$

For $A\subseteq {\mathbb F}_2^n$ let $$ Q(A)=\{\alpha+\beta\mid \alpha,\beta \in A,\ \alpha\neq\beta \}. $$ I want to prove or disprove that if $|A|=2^k+1$ for some integer $k$, then $$ ...
5
votes
3answers
252 views

Sets of natural numbers with finite intersections and divergent sums of reciprocals

Does there exist an uncountable collection $\Lambda$ of infinite subsets of the set of natural numbers such that (i) any two distinct subsets in the collection have a finite intersection and (ii) the ...
2
votes
0answers
94 views

Applications of Freiman's theorem?

What are some interesting applications of Freiman's theorem or, better-yet, its recent generalizations (eg Green-Ruzsa) that could be included in a graduate course in additive combinatorics? I'm ...
7
votes
2answers
556 views

Most dense subset of numbers that avoids arbitrarily long arithmetic progressions

The famous Green-Tao theorem says that there exist arbitrarily long sequences of primes in arithmetic progression. I am wondering: How dense can a subset $S \subset \mathbb{N}$ be and still avoid ...
3
votes
0answers
218 views

Solving a doubly exponential generating function

I am analyzing the average time complexity of some algorithm on some probabilistic model, and I've come to a doubly exponential sequence for which I cannot find corresponding generating function. I ...
3
votes
2answers
200 views

Number of subsum of a given set of integers

I am asking myself for few days the following but I can't find any references, although I am pretty sure this was already studied, because it seems quite natural: Given n integers $(e_i)$ chosen ...
3
votes
1answer
139 views

Packing bounds for sumsets, or, very discrete balls

Let $D\subset \mathbb{F}_2^n$ with $D=-D$ and $0\in D$. Write $k D$ for the set of all sums of $k$ (not necessarily distinct) elements of $D$. (This is the "ball" in the title.) Now let $d(g,h)$ be ...
7
votes
3answers
185 views

Polynomial expressions of roots of unity with integer norm

Say a nonconstant polynomial $p(z)$ is $k$-magical if it satisfies the following properties: $p$ is of the form $$p(z) = a_{k-1} z^{k-1} + a_{k-2} z^{k-2} + \cdots + a_1 z + 1$$ where each $a_i \in ...
11
votes
0answers
318 views

How large must $A$ be if $\{1, \ldots, N\} \subseteq A-A$?

Given a positive integer $N$, what is the size of the smallest set of integers $A$ such that, for any integer $1 \leq k \leq N$, we can find two integers $x, y \in A$ such that $x - y = k$? (An ...
1
vote
1answer
101 views

asymptotic for restricted partitions

Let $m$ and $n$ be two positive integers and denote by $P(n,m)$ the number of partitions of $n$ into $m$ non-negative integers. Is there an asymptotic formula for $P(n,m)$ ?? Any reference is ...
2
votes
2answers
165 views

Functions representable as a sum of two permutations of Z/nZ

Let $\ f:Z/n\rightarrow Z/n\ $ be a function such that $\ \sum_{i\in Z/n}\,f(i)=0.\ $ Is it true that $\ f\ $ can be represented as a sum of two permutations of Z/nZ?
3
votes
1answer
141 views

How to generate $n$ FP32 rationals s.t. no two distinct k-el. subsets have same sum?

First some Background: I have lots and lots of integer matrices, whose rows are $k$-combinations (without repetitions and sorted) of numbers from the set $S:=\{1,...,n\}$ and needed to be compared ...
4
votes
0answers
130 views

Reduction argument from a general vertex set V(G) to a prime power in Prof. Keevash's proof on the Existence of Designs

The proof flow of the paper "On the Existence of Designs" by Prof. Keevash as I understand it is the following: -- Reduction from the general case to $V = \mathbb{F}_{p^a}$ (Lemma 6.3) -- Covering ...
-1
votes
1answer
181 views

Collecting terms of a linear expression with nested sums and combinatorics in coefficients

I need to collect the $\Pr(\cdot)$ terms of the following expression: $\sum_{m=3}^{n}\frac{g_{m}\left( \cdot \right) }{\left( \sqrt{\theta \left( 1-\theta \right) }\right) ^{m}}\left[ ...
1
vote
1answer
204 views

every arithmetic progression contains a sequence of $k$ “consecutive” primes for possibly all natural numbers $k$?

I ask the same question here:http://math.stackexchange.com/q/1019404/192097 writing a little better the previous question: it´s true that if we let $a$ and $b$ be coprime integers, then the ...
1
vote
0answers
143 views

Sets of coprime numbers

Consider the set $\{0, 3, 7, 15\}$ of four integers. If you add each of these numbers to a fixed power of 2, then the resulting four numbers are pairwise coprime. For example, $\{4, 7, 11, 19\}$ are ...
5
votes
0answers
170 views

The sum of all the elements of every non empty subset of $A$ is not a multiple of $n$

Let $N=\{1,2,\ldots ,n\},n>1$. We wish to construct a set $A\subseteq N$ with the property: The sum of all the elements of every non empty subset of $A$ is not a multiple of $n$. ...
0
votes
0answers
72 views

Integral representation of the function

I try find integral representation to following function ($d_1<d_2$ and $d_2-d_1=1(\mod 2)$ $f(d_1,d_2)=\frac{(-1)^{\frac{d_2-d_1-1}{2}}}{2^{d_1-1} d_1!}\sum_{k=[\frac{d_1}{2}]+1}^{ d_1} { d_1 ...
1
vote
1answer
99 views

Finding a sufficiently large complete bipartite subgraph using matrix counting

I'm trying to reconstruct the proof using matrix counting that there exists two subsets $A,B$ of $\{1,\cdots,N\}$ with $\#A=\#B$ such that for any $a\in A$ and $b\in B$, $a+b$ is prime, and $\#A=\#B$ ...
0
votes
0answers
59 views

Sumset of parallel arithmetic progressions in Euclidean space

Let $A$ be a finite subset of $\mathbb R^n$ such that dim $A=n$ ($A$ is not contained in any lower dimensional hyperplane). It is a known result from Freiman that the size of the sumset $A+A$ is lower ...
6
votes
0answers
79 views

Why have most maximal cliques of Paley graphs odd size?

I ask this question mainly by curiosity. See here for definitions and a plot of the clique numbers of the Paley graphs for the primes $p\equiv 1 \pmod 4$ up to $10000$. Is there an ...
1
vote
1answer
107 views

Expression and growth bound for $r_{p^m,k}(n)$

Let's define , $$R_{p^m,k}(n)=\#\{(a_1,\dots,a_k)\in\mathbb{Z}^k:\sum_{i=1}^ka_i^2\le n \ \text{and} \ p^m|\sum_{i=1}^ka_i^2\}$$ what will be growth bound of $R_{p^m,k}(n)$? This can be thought as a ...
0
votes
1answer
61 views

Monotonicity of the gap of permutated sequence

Let $a$ be an arbitrary sequence and denote by $\mbox{gap}_k(a) = a_{(k)} - a_{(k+1)}$, where $a_{(k)}$ is the $k$th largest component of $a$. Of course, $k+1$ should be no larger than the length of ...
2
votes
1answer
161 views

Growth of $r_k(n)$

What is the best known growth bound of $r_k(n)$, where $$r_k(n)=\#\{(a_1,\dots,a_k\in\mathbb{Z}^k:\sum_{i=1}^ka_i^2=n\}?$$ Please provide some reference if known. Thanks.
3
votes
0answers
145 views

Subgroup cliques in the Paley graph

It is a famous open problem to estimate non-trivially, for a prime $p\equiv 1\pmod 4$, the largest size of a subset $A\subset{\mathbb F}_p$ such that the difference of any two elements of $A$ is a ...
1
vote
1answer
464 views

Subset of the integers with certain properties

How would one find the maximal $n$ such that there exists an $n$-subset $S$ of $\mathbb{Z}^+$ such that $\forall A\subseteq S, \sum_{a\in A}a$ is either a perfect square or a perfect cube, or can one ...
5
votes
3answers
402 views

Any rigorous way to claim that sums with repeat summands are few?

Let $B \subset \mathbb{Z}^+$. Define $r_{B,h}(n)$ to be the number of ways of writing $n$ as the sum of $h$ elements of $B$ and $R_{B,h}(n)$ the number of ways to write $n$ as the sum of $h$ DISTINCT ...
1
vote
0answers
45 views

$B_k[1]$ sets with smallest possible $m = max B_k[1]$ for given $k$ and $n = |B_k[1]|$ elements

Sidon sets are sets $A \subset \mathbb{N}$ such that for all $a_j,b_j \in A$ holds $$a_1+a_2=b_1+b_2 \iff \{a_1,a_2\}=\{b_1,b_2\}$$ Thus if you know the sum of two elements, you know which elements ...
11
votes
2answers
639 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 ...
4
votes
2answers
207 views

Intuition for Freiman dimension

Let $A\subset G$ and $B\subset H$ be subsets of abelian groups. We say that a map $f\colon A\to B$ is a Freiman homomorphism if for all $a_1,\dots, a_4\in A$ one has ...
4
votes
1answer
82 views

Spectrum of image of a Freiman Homomorphism

Let $A\subset \mathbb{F}_p^n$ along with a k-Freiman isomorphism $\phi:A \rightarrow \mathbb{F}_p^m$ for $A$. Can we say any meaningful statement about the structure of $Spec_\alpha(\phi(A))$ ...
6
votes
5answers
605 views

What makes a set random?

There are many results in number theory, where the existence of some $B \subseteq \mathbb{N}$ with certain properties is proved by a probabilistic argument employing "random sets". One such example ...
0
votes
0answers
76 views

latest classification of difference sets

I am looking for a reference including the last classification of difference sets and almost difference sets. Would you mind letting me know some of them? The recent ones are preferred.
23
votes
1answer
563 views

integers which are sums of binomial coefficients: $\sum_i {n \choose k_i}$

Let $n$ be an integer. For $S$ a subset of $\{0,\dots,n\}$, define $$m(S) = \sum_{k \in S} {n \choose k}.$$ Let $M_n$ be the set of integers of the form $m(S)$ for all sets $S \subset \{0,\dots,n\}$. ...
2
votes
0answers
184 views

Can the affine sieve be used to sieve for $k$-free values?

The affine sieve, developed initially by Bourgain-Gamburd-Sarnak in the paper "Affine linear sieve, expanders, and sum-product" published in Inventiones Mathematicae in 2010, deals generally with the ...
5
votes
2answers
280 views

Size of distinct sums in A

Let $G$ be an abelian group. Let $A\subset G$ be a finite set. $\sum_A$ is defined as: $$\left\{\sum_{b\in B}b \mid B\subset A\right\}$$ Is there any result similar to Freiman's Theorem for $\sum_A$? ...
4
votes
1answer
247 views

Examples of specializations of elementary symmetric polynomials

Let $\mathcal{S}_{x}=\{x_{1,},x_{2},\ldots x_{n}\}$ be a set of $n$ indeterminates. The $h^{th}$elementary symmetric polynomial is the sum of all monomials with $h$ factors \begin{eqnarray*} ...
30
votes
4answers
2k views

Cliques, Paley graphs and quadratic residues

A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs. If p=1 mod 4 is a prime, we can define the ...