**1**

vote

**1**answer

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

**0**

votes

**1**answer

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

**18**

votes

**0**answers

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

**11**

votes

**0**answers

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

**10**

votes

**0**answers

399 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

509 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

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

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

**7**

votes

**0**answers

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

**6**

votes

**0**answers

307 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

136 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

128 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

534 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

339 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

85 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

97 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

59 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

81 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

114 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

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

**3**

votes

**0**answers

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

**3**

votes

**0**answers

197 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

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

**3**

votes

**0**answers

307 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

146 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

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

**2**

votes

**0**answers

246 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

921 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

36 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

63 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

134 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

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

**1**

vote

**0**answers

92 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

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

65 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

59 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

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

**0**

votes

**0**answers

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

**0**

votes

**0**answers

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

**0**

votes

**0**answers

405 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

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