**5**

votes

**3**answers

519 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

**0**answers

331 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

**1**answer

304 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

**1**answer

356 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

**1**answer

305 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

**1**answer

348 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

**1**answer

183 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

**2**answers

88 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

**0**answers

237 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

**1**answer

470 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

**1**answer

154 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

**1**answer

177 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

**1**answer

278 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

**0**answers

101 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 ...

**22**

votes

**2**answers

1k 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

**2**answers

121 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

**2**answers

413 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

**1**answer

162 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

**1**answer

473 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

**0**answers

155 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

**2**answers

251 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) ...

**14**

votes

**1**answer

782 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

**1**answer

147 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

**0**answers

33 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

**1**answer

313 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

**0**answers

115 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

**3**answers

587 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 ...

**19**

votes

**0**answers

407 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

**1**answer

363 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

**1**answer

84 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

**0**answers

389 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

**1**answer

257 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

**2**answers

366 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

**1**answer

229 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

**0**answers

150 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

**1**answer

144 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

**1**answer

338 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 ...

**30**

votes

**2**answers

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

**1**answer

751 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

**0**answers

542 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

**0**answers

554 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

**3**answers

331 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

**2**answers

814 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

**0**answers

212 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

**0**answers

113 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

**0**answers

124 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

**2**answers

320 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

**1**answer

237 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

**0**answers

490 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

**0**answers

269 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 ...