**3**

votes

**1**answer

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

**19**

votes

**0**answers

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

**12**

votes

**0**answers

364 views

### Correlation of Fourier transforms of characteristic functions

Let $A$ and $B$ ($A\subset B$) be subsets of a finite abelian group $G$. (For the sake of argument, you can take $G$ to be $\mathbb{Z}/p\mathbb{Z}$ for large $p$, say.) Write $1_S$ for the ...

**11**

votes

**0**answers

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

**10**

votes

**0**answers

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

**9**

votes

**0**answers

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

**8**

votes

**0**answers

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

**8**

votes

**0**answers

135 views

### Erdös-Fuchs Theorem for multivariate linear forms

Let $A$ be an infinite set of positive integers, and denote by $r(n)$ the number of solutions to the equation $a+a'=n$, with $a,\, a' \in A$.
It is not very difficult to show that if $r(n) > 0$ ...

**7**

votes

**0**answers

190 views

### A strong sum-product “for translates” in finite fields

In the course of some recent research, I've sketched out a proof of the following result. My basis question is: is the result interesting?
Proposition There exists an absolute constant $c$ such ...

**6**

votes

**0**answers

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

**6**

votes

**0**answers

317 views

### Small maximal sets with no 3-AP?

Everyone knows about the problem of finding the largest set in 1,2,...,N which contains no arithmetic progression of length 3.....what happens if we look at the set which is the
smallest maximal ...

**5**

votes

**0**answers

169 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$.
...

**5**

votes

**0**answers

146 views

### Distribution of subset-sums

Let $A$ be a set of $n$ integers uniformly distributed in $\{0,\dots,N-1\}$. Let $S$ be the set of subset-sums modulo $N$ of $A$. Let $f_{n,N}(k)$ be the probability that $|S|=k$.
Is there an ...

**5**

votes

**0**answers

143 views

### Other applications of the 'increment' approach

I would like to hear about other instances of the so-called 'increments' approach, first used by Roth to prove that a subset of $\mathbb{N}$ of positive upper density contained infinitely many ...

**5**

votes

**0**answers

558 views

### Expectation of Gowers norm

This was a problem that came up during a course on Analytic Combinatorics that I had taken this semester. Here's the problem:
Let $\mathbf{F}$ be the set of boolean functions, $f: \mathbb{F}_2^n ...

**4**

votes

**0**answers

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

**4**

votes

**0**answers

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

**3**

votes

**0**answers

212 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

**0**answers

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

**3**

votes

**0**answers

87 views

### Sets of polynomials with restricted set of products

Let $F = \{f_1, ..., f_n\}$ be a set of distinct monic polynomials (and thus also $f_i^2$ are distinct). Let $F' = \{f_i f_j: i \neq j\}$ be the set of pairwise products of all distinct elements from ...

**3**

votes

**0**answers

100 views

### Number cubes with consecutive line sums

This is barely of research interest, but I'd classify it as a curiosity with connections to combinatorics.
The problem is to place integers in an $n \times n \times n$ array so that all $3n^2$ line ...

**3**

votes

**0**answers

62 views

### Distribution of the evaluation (at a non-trivial root of -1) of polynomials with small coefficients

When we studied some cryptographic protocol, we came accross the following problem, which seems linked to the uniformity of the residues of small multiplicative subgroups of $\mathbb{F}_q$.
Problem
...

**3**

votes

**0**answers

90 views

### “Pseudo-random” subsets of additive bases

We say that a subset $B \subset \mathbb{N}$ is an (asymptotic) additive basis of order $k$ if the set $kB = B + \cdots + B = \mathbb{N} \setminus C$, where $C$ is a finite set of positive integers. ...

**3**

votes

**0**answers

120 views

### Doubling for Sumset of the same set

Let $G$ ($G=\mathbb{Z}^n_2$ for my case) be a additive group and $A$ be a subset of $G$. For any set $S\subseteq G$ define its doubling as $$\sigma (S)=\dfrac{|S+S|}{|S|}$$
Suppose $A$ has small ...

**3**

votes

**0**answers

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

**3**

votes

**0**answers

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

**3**

votes

**0**answers

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

**3**

votes

**0**answers

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

**3**

votes

**0**answers

313 views

### A question about Erdos thin bases

Let $B \subset \mathbb{N}$ be an additive basis of order $h$. Define $r_{B,h}(n)$ to be the number of ways $n$ can be written as a sum of $h$ elements of $B$. In particular, $B$ is a basis of order ...

**2**

votes

**0**answers

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

**2**

votes

**0**answers

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

**2**

votes

**0**answers

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

**2**

votes

**0**answers

248 views

### Prime divisors of the difference set

Fix $c\in(0,1)$, and let $N$ be a (large) positive integer. Given a set $A=\{0=a_1<\dots<a_n=N\}$ of density $\alpha:=n/N>c$ with $\gcd(A)=1$, I want to find a prime dividing as few ...

**2**

votes

**0**answers

942 views

### Fun question in additive combinatorics

It is easy to see that for a finite set of integers $A$ of cardinality $n$, the cardinality of the sumset $A+A$ satisfies
$$
2n-1\leq |A+A|\leq \frac{n(n+1)}{2}.
$$
The lower bound is essentially ...

**1**

vote

**0**answers

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

**1**

vote

**0**answers

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

**1**

vote

**0**answers

68 views

### Stronger condition than being a normal polytope?

A polytope $P$ with integer vertices is called normal if
for every $p = \sum_j a_j p_j $ such that $a_j \geq 0$, $\sum_j a_j = k \in \mathbb{N}$,
$p_j$ are vertices of $P$ and $p$ is an integer ...

**1**

vote

**0**answers

145 views

### Finite fields: alternating sums of values of polynomials

Notation
In what follows let $p$ be a (odd, if needed) prime, $e$ a positive integer, $q = p^e$; $\mathbb{F}_q$ will denote a finite field with $q$ elements whose prime subfield will be denoted as ...

**1**

vote

**0**answers

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

**1**

vote

**0**answers

106 views

### Examples of using additive structure to analyze size of a set mod some ideal?

There are examples of proofs that analyze the structure of some set $S$ of integers by looking at the size of the set mod some positive integer $n$ (for example, the $3k-3$ theorem.)
Are there ...

**0**

votes

**0**answers

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

**0**

votes

**0**answers

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

**0**

votes

**0**answers

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

**0**

votes

**0**answers

69 views

### Cover one finite subset of integers by another one

Let $A$, $B$ be two finite subsets of integers. We denote by $C(A, B)$ the minimum number of shifts of $A$ to cover $B$. More formally, it can be written as
$$
C(A, B)=\min\{|S|: S\subseteq ...

**0**

votes

**0**answers

66 views

### $\sum_{a\in A} r(a)$, where $A\subseteq\mathbb{Z}_n$ and $r(a)$ is the number of representations of $a$ as sum of two elements from $A$

Reading Seva's answer to this question, I got lost at the line relating $\sum_{a\in A} r(a)$ to $|A\cap 2A|$. More precisely, restating the problem:
Let $A\subseteq\mathbb{Z}_n$ be an set of ...

**0**

votes

**0**answers

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

**0**

votes

**0**answers

30 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, ...

**0**

votes

**0**answers

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

**0**

votes

**0**answers

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

**0**

votes

**0**answers

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