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

5
votes
3answers
511 views

A question on residues mod an even integer

I posted the question here, but it seems to be more difficult than I expected. So I think it may be suited for MO. (Another reason is that the answer may hopefully give solution to the question on ...
1
vote
0answers
300 views

Green-Tao style theorem for quadratic regressions (Ulam Spiral)

This is a naive question about number theory. Looking at an Ulam spiral which illustrates primes of the form e.g. $4x^2-2x+c$ and other quadratic equations $ax^2+bx+c$, with $c>0$, there appears a ...
8
votes
1answer
286 views

A Balog-Szemeredi-Gowers-type question

A nice Lemma due to Konyagin asserts that for any subset $B \subset \mathbb{F}_p$ holds $$ |B.B - B.B + B.B - B.B + B.B - B.B| \geq \frac{1}{2}\min\{p, |B|^2 \}, $$ where the standard notation for the ...
2
votes
1answer
341 views

Maximal size of an almost-disjoint linearly independent family in $K^{\mathbb{N}}$

Let $K$ be a field, say infinite, and denote by $L$ the $K$-vector space $K^{\mathbb{N}}$. What is the maximal cardinality of a $K$-linearly independent subset $X$ of $L$ such that any two distinct ...
1
vote
1answer
292 views

Valid Difference Sets

Suppose $$ P \subseteq \{1,2,\dots,N\},\quad |P| = K $$ We calculate the differences as: $$ d=p_i-p_j\mod N,\quad i\ne j $$ Now let $a_d$ denote the number of occurrence of $d$ (for $d = 0, 1, 2, ...
3
votes
1answer
321 views

A reference for this possibly well-known fact concerning the Kakeya conjecture?

I believe I have read or heard somewhere that the Kakeya conjecture would follow from appropriate lower bounds for the minimal size of a subset of $\{ 1 , \cdots , N\}$ which contains a translate of ...
1
vote
1answer
166 views

Does the asymptotic formula for Partitions into parts <c exist?

A partition of $n$ is a weakly decreasing tuple of numbers $(\lambda_1,\lambda_2,\lambda_3,....\lambda_k)$ whose sum is $n.$ A natural problem studied is counting partitions whose summands ...
1
vote
2answers
83 views

Generalization of Rado's Single Equation theorem

Yesterday I came up with a problem: Can we color each point of the plane with finitely many colors such that there doesn't exist any monochromatic regular polygonal? But I found the problem is too ...
0
votes
0answers
163 views

Greedy sequences without k-term arithmetic progressions

If $S_k$ is the greedy sequence with no length-k arithmetic subsequence, (ie $S_3$ = A003278 , $S_4$ = A005837 , $S_5$ = A020655 ), is it guaranteed that any other sequence $a$ with no length-k ...
5
votes
1answer
452 views

Difference Sets

Suppose $$ P \subseteq \{1,2,\dots,N\},\quad |P| = K $$ We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$ Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...
3
votes
1answer
142 views

Non-asymptotically densest progression-free sets

For the context of this question, a progression-free set is a subset of integers that does not contain length-three arithmetic progressions. For large $N$, it is known that $[N] = \{1, \ldots, N\}$ ...
4
votes
1answer
167 views

Set of small numbers with distinct $k$-sums

Let $A$ be a set of $n$ positive integers with distinct $k$-sums. In other words, if $a_1\le\cdots\le a_k$ and $b_1\le\cdots\le b_k$ are elements of $A$ such that $a_1+\cdots+a_k=b_1+\cdots+b_k$, then ...
1
vote
1answer
247 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 ...
3
votes
0answers
92 views

Closest sumset to a set

Suppose $A$ is a subset of the finite field with $p$ elements. What is the best approximation of $A$ by a sumset $B+C$ in the sense that $|A\Delta (B+C)|$ is minimal? Of course if $B=A-x$ and ...
21
votes
2answers
978 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}$ ...
3
votes
2answers
112 views

A measure of closure under sumset?

Let $G$ be an Abelian group. Let $A \subseteq G$. In additive combinatorics, one of the primary measures of the additive structure of $A$ is its additive energy, defined as $E(A) = ...
4
votes
2answers
394 views

Average involving the Euler phi function

Does $$\frac{1}{N^2}\sum _{d=1}^N \log d \sum _{n=1}^{N/d} \frac{\phi(n)}{\log (dn)},$$ converges or not when $N$ goes to infinity?
1
vote
1answer
149 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
391 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 + ...
1
vote
0answers
153 views

Estimates for the size of the product set [n].[n] [duplicate]

Possible Duplicate: Number of elements in the set {1,…,n}*{1,..,n} Writing $[n]$ for the set $\lbrace1,2,...,n\rbrace$, let $P_n$ denote the product set $[n].[n]$, i.e. $$ P_n = ...
0
votes
2answers
244 views

Solution in distinct elements for a system of $n$ equations over finite fields

The following problem is motivated by pure curiosity; it is not a part of any research project and I do not have any applications. Problem: Let $\{y_1 , y_2 , \dots, y_n \}$ be arbitrary (distinct) ...
12
votes
1answer
621 views

On the $L^1$-norm of certain exponential sums.

I am stuck with an elementary-looking problem, which does not belong to my usual field of research so I eventually decided to ask it on MO. Let $S$ be a finite set of integers. For $P$ a subset of ...
3
votes
1answer
141 views

existence of arithmetic progression of nonzero density

This is a stronger version to Szemerédi's theorem. Let $C : \mathbb{N}\rightarrow 2^{\mathbb{N}}$ be a choice function such that $C(n)$ is a subset of $\{1,...,n\}$ with size at least $\frac{n}{M}$ ...
0
votes
0answers
28 views

Minimum number of solutions in a system of equalities and non-equalities

Let $k<N$ and $P_1, ..., P_{2k+1}, \lambda_1, ..., \lambda_k$ be elements of a finite group $G$ of size $N$. Find the minimum number of solution of the system $$P_{2i} + P_{2i+1} = \lambda_i, ...
1
vote
1answer
310 views

About a sumset in $\mathbb{Z}_{2k}$

Suppose $U\subset\mathbb{Z}_{2k}$ with $|U|=k$. Let $U^c$ denote the complement of $U$. Let $v\in \mathbb{Z}_{2k}^{\times}$. How much is it known about $U+vU^c$? For example: When $U+v\complement U ...
3
votes
0answers
106 views

Bounds on difference sets of relatively dense A \subseteq {1, …, n}

Let $A \subseteq \{1, \dots, n\}$ and let $A-A = \{a-b | a,b \in A\}$. Is it possible to obtain a general bound of the form $|A - A| = O(n^\beta)$ for some $\beta < 1$? If not, can something like ...
4
votes
3answers
454 views

Selecting $k$ integers from an interval $[0, N]$ to maximize the minimum difference between pairwise sums

I have an optimization problem where I need to select $k$ integers over the interval $[0, N]$ s.t. I maximize the minimum difference between any pairwise sum of the $k$ integers (where we also include ...
18
votes
0answers
351 views

probability of zero subset sum

Almost 17 years ago, I asked the following question on USENET, motivated by a method in numerology (I kid you not). Pick integers $n \ge 2$, $k \ge 1$. Toss $n$ $k$-sided dice. The sides of each die ...
1
vote
1answer
323 views

Generalizations of Cauchy-Davenport Theorem

The Cauchy-Davenport Theorem says that if $A_1, \ldots, A_k$ are subsets of ${\mathbb Z}_p$, $p$ prime, then $| \sum_i A_i | \geq \min (p, \sum_i |A_i| -k +1)$. I am looking for a generalization that ...
0
votes
1answer
82 views

sum of a binomial-weighted entity

Does anybody know a closed-form solution for the following expression (N>=1)? I don't even know where to begin with the i+n denominator. Sum of i=0 to n Combin(n,i) * (2i/(i+n)) / (2^n)
4
votes
0answers
337 views

Largest set of integers without 3-term arithmetic progressions mod $n$

I am interested in a sharp bound on the largest possible size $e_3({\boldsymbol{Z}_n})$ of a subset $S \subset \boldsymbol{Z}_n$ such that for any three distinct elements $a, b, c \in S$ we have $a+b ...
6
votes
1answer
243 views

Recovering Sidon sets from difference sets, part 2.

This is inspired by a recent question. A set $A \subset \mathbb{Z}/n\mathbb{Z}$ with $|A|=m$ is a Sidon set if all the pairwise sums of distinct elements are unequal: $A+A=\{a+a' \mid a,a' \in A, a ...
2
votes
2answers
339 views

Recovering Sidon sets from difference sets

How can I recover a Sidon set $A\subseteq \mathbb{Z}/n\mathbb{Z}$ from the set $A-A\subseteq \mathbb{Z}/n\mathbb{Z}$? Is it even unique? (up to translation and reflection) ($A-A$ stands for the set ...
4
votes
1answer
211 views

Additive energy of random sets

Given two random sets $A,B$ in a finite field (say $x\in A$ independently and with probability $1/2$), what is known about the additive energy $E(A,B)=|\{(a,a',b,b')\in A\times A\times B\times B: ...
0
votes
0answers
136 views

upper bound on the size of sumset of lattice points

Let $\Lambda$ be a lattice (discrete additive subgroup) in $\mathbb R^n$ ($n\geq 2$). In my problem, $\Lambda$ lies in a $k$ dimensional ($1< k\leq n$) subspace of $\mathbb R^n$. Let $A\subset ...
1
vote
1answer
134 views

Is there a function that determines the rank of a multiset after inserting another element?

For instance, lets say we have a set $S = (0,1)$ containing $n = 2$ distinct elements. The multiset $M = (1,1)$ has rank $5$ because there are $4$ multisets less than it based on lexicographic ...
3
votes
1answer
285 views

Additive set with small sum set and large difference set

I have a question! Can someone explain how (the intuition, method?) one can try to construct an additive set of cardinality $N$ with a small sum set (around $N$) and a very large difference set ...
23
votes
2answers
2k views

Number of elements in the set $\{1,\cdots,n\}\times\{1,\cdots,n\}$

Let $A_n=\{a\cdot b : a,b \in \mathbb{N}, a,b\leq n\}$. Are there any estimates for $|A_n|$? Will it be $o(n^2)$?
5
votes
1answer
711 views

Graham-Rothschild via Hales-Jewett

I am currently reading the recent preprint of Dodos, Kanellopoulos, Tyros, where the ambitiously short proof of Density Hales Jewett theorem is provided. The important ingredient is Graham-Rothschild ...
9
votes
0answers
508 views

Cliques in the Paley graph and a problem of Sarkozy

The following question is motivated by pure curiosity; it is not a part of any research project and I do not have any applications. The question comes as an interpolation between two notoriously ...
0
votes
0answers
400 views

Calculating the Shapley value in a weighted voting game.

Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
4
votes
3answers
310 views

L^2-Flattening Lemma

I am reading a significant paper of Bourgain and Gamburd on "Uniform expansion bounds for Cayley graphs of $\mathrm{SL}_2(\Bbb{F}_p)$". They have proven a proposition which in their new papers they ...
3
votes
2answers
798 views

There exists B subset A, |B| = log n, A \cap 2*B = \emptyset

This is exercise 1.8.1 of Additive Combinatorics. Problem Given $A \in Z^+$ a set of $n$ different integers. Prove that there exists $B\subset A$, $|B| = \Omega ( \log n )$, s.t. $A \cap 2*B = ...
3
votes
0answers
195 views

Convex subsets of sumsets

There's a famous old problem in additive number theory which asks whether, for any $\epsilon > 0$, if $B$ is a 2-basis for the set $A =$ {$1^2,2^2,...,n^2$}, i.e.: a set for which $B+B \supseteq ...
2
votes
0answers
106 views

Lower bound on P(Y > 3/2 E(Y)) where Y = # of triangles in graph

Context This is exercise 1.7.1 of Tao/Vu's Additive Combinatorics, generally considered a graduate level math textbook. My question is not "How do I solve this exercise?" My question is "What is ...
3
votes
0answers
114 views

Other interesting examples of pseudo-random measures

Here we use the notion of pseudo-randomness (or variant of) used in the proof of the Green-Tao theorem. In particular, we say a measure $\nu : \mathbb{Z}_N \rightarrow \mathbb{R}^+$ is pseudo-random ...
7
votes
2answers
316 views

Elementary Proof of Basis of Order k

Context According to the FAQ, questions of the form "the sorts of questions you come across when you're writing or reading articles or graduate level books" are acceptable. This falls into the ...
1
vote
1answer
220 views

Technique: Compactness => (Finite -> Reals)

Context I'm studying a classical results of Erdos and Lovasz, on colorings of the real line. The theorem to be proved is as follows: Let $m, k$ be two positive integers satisfying: ...
10
votes
0answers
388 views

What are the limits of the Erdős-Rankin method for covering intervals by arithmetic progressions?

To construct gaps between primes which are marginally larger than average, Erdős and Rankin covered an interval $[1,y]$ with arithmetic progressions with prime differences. A nice short exposition is ...
0
votes
0answers
250 views

Kakeya problem and arithmetic progressions

Here's something I also posted on Stackexchange recently. It's very related to the Kakeya problem, yet I fail to see why this is true. It goes like this: Let $r > 2$ be an integer parameter. Let ...