**2**

votes

**1**answer

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

**10**

votes

**2**answers

723 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

**0**answers

246 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

**1**answer

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

**3**

votes

**2**answers

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

**9**

votes

**3**answers

277 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

**0**answers

336 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

**1**answer

134 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

**2**answers

196 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

**1**answer

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

**13**

votes

**1**answer

391 views

### Minimal “sumset basis” in the discrete linear space $\mathbb F_2^n$

For a set $C\subseteq \mathbb F_2^n$, let $2C=C+C:=\{\alpha+\beta\colon \alpha,\beta\in C\}$.
I want to find $C$ of the smallest possible size such that $2C=\mathbb F_2^n$. Let $m(n)$ be the size of a ...

**1**

vote

**0**answers

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

**4**

votes

**0**answers

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

vote

**1**answer

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

**5**

votes

**0**answers

177 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

**0**answers

73 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

**1**answer

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

**6**

votes

**0**answers

85 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

**1**answer

108 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

**1**answer

62 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

**1**answer

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

**0**answers

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

**2**

votes

**2**answers

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

**1**

vote

**1**answer

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

**1**

vote

**0**answers

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

**4**

votes

**1**answer

95 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))$ ...

**5**

votes

**2**answers

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

**23**

votes

**1**answer

591 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

**0**answers

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

**13**

votes

**2**answers

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

**5**

votes

**2**answers

302 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$? ...

**7**

votes

**0**answers

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

**5**

votes

**1**answer

265 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*}
...

**6**

votes

**5**answers

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

**10**

votes

**2**answers

282 views

### Large sets $X \subseteq \mathbb{Z}_2^n$ with $X+X \ne \mathbb{Z}_2^n$

I've come across a seemingly natural question in additive combinatorics to which I can't find the answer in the literature. I would like to know if, given an $\alpha > 0$ and large $n$, there are ...

**3**

votes

**0**answers

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

**24**

votes

**3**answers

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

**-1**

votes

**1**answer

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

**4**

votes

**1**answer

305 views

### Circle method on things other than the integers

The circle method is often used to estimate the number of solutions to the equation $$x_1 + x_2 + ... x_k = N$$ if for all $i$ $x_i\in A\subseteq\mathbb{N}_0$ and some subset of the nonnegative ...

**0**

votes

**0**answers

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

**3**

votes

**1**answer

161 views

### Is every sufficiently dense well mixed set an additive basis?

Let $B \subset \mathbb{N}$ be a set of natural numbers such that $|B \cap [1,N]| \sim N^\gamma$, for some $\gamma > 0$ with the following property:
For any pair of positive integers $k,n$ we ...

**3**

votes

**0**answers

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

**1**

vote

**0**answers

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

**5**

votes

**1**answer

455 views

### Balog-Szemeredi-Gowers with dilates of sets

All sets are assumed to be finite subsets of the integers.
The additive energy of two sets $E(A,B)$ is defined as the number of solutions to $a+b=a'+b'$ with $a,a'\in A$ and $b,b'\in B$. The ...

**5**

votes

**1**answer

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

**20**

votes

**3**answers

648 views

### A sumset inequality

A friend asked me the following problem:
Is it true that for every $X\subset A\subset \mathbb{Z}$, where $A$ is finite and $X$ is non-empty, that $$\frac{|A+X|}{|X|}\geq \frac{|A+A|}{|A|}?$$
...

**5**

votes

**1**answer

276 views

### Normal polytopes - counterexample?

An integral polytope $P$ is normal if all lattice points inside the integer dilation $kP$ can be expressed as $p_1+p_2+\dots+p_k$, where $p_i \in P$ are lattice points.
I am looking for an example ...

**9**

votes

**2**answers

589 views

### Finite field Szemeredi-Trotter theorem with unequal number of points and lines

My question concerns the Szemerédi-Trotter theorem in $\mathbb{F}_q^2$. If we have $m$ points and $n$ lines in $\mathbb{F}_q^2$, then by Cauchy-Schwartz the number of point-line incidences is as most ...

**20**

votes

**4**answers

2k views

### Number of vectors so that no two subset sums are equal

Consider all $10$-tuple vectors each element of which is either $1$ or $0$. It is very easy to select a set $v_1,\dots,v_{10}= S$ of $10$ such vectors so that no two distinct subsets of vectors $S_1 ...

**8**

votes

**0**answers

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