**1**

vote

**1**answer

114 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

86 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

110 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

64 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

164 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

157 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

528 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

516 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

52 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

98 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

238 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
$$f(a_1)+f(a_2)=f(a_3)+f(a_4),\...

**23**

votes

**1**answer

603 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

235 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

935 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

309 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

226 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

276 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*}
e_{h}(\...

**6**

votes

**5**answers

636 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

288 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

93 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

589 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 $a_1,...

**-1**

votes

**1**answer

189 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[ \sum_{j=2}^{m-1}...

**4**

votes

**1**answer

320 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

76 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 B-A,~\...

**3**

votes

**1**answer

183 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

115 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

78 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

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

**9**

votes

**1**answer

1k 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 \mathbb{N}...

**20**

votes

**3**answers

684 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

292 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 $P$...

**9**

votes

**2**answers

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

**19**

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

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

**0**

votes

**0**answers

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

**5**

votes

**0**answers

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

**3**

votes

**0**answers

3k views

### How many combinations does Android pattern have? [closed]

Rules-
1) At-least 4 and at-max 9 dots must be connected.
2) There can be no jumps
3) Once a dot is crossed, you can jump over it.

**3**

votes

**0**answers

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

**21**

votes

**3**answers

2k views

### How many different numbers can be obtained as product of first $n$ natural numbers?

Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set
$\{1^{a_1} \cdot 2^{...

**4**

votes

**1**answer

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

**4**

votes

**1**answer

777 views

### a conjecture in sum-free sets

Let $ A $ be a set of non-zero integers. Then $A$ contains a sum-free subset $B$ of size $ |B|> \frac{|A|}{3} $ (a result of Erdős). It is conjectured that RHS can be improved to $\frac{|A|}{3} +...

**12**

votes

**0**answers

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

**13**

votes

**3**answers

853 views

### Density of all n such that 2^n-1 is square free

Is it true that the set $$S:=\{n\in \mathbb N\ |\ 2^n-1 \ \mbox{ is square free}\}$$ has positive density? What can we say when we replace $2^n-1$ with $\frac{a^n-1}{a-1}$?

**20**

votes

**1**answer

670 views

### Avoiding multiples of $p$

Let $p$ be a prime number and $P=\{1,2,...,p-1\}$
In how many ways we can sum all the elements of $P$ in such a way that we will reach a multiple of $p$
only when we sum the last summand?
For ...

**9**

votes

**1**answer

564 views

### 4 squares almost in an arithmetic progression

Does there exist infinitely many coprime pairs of integers x,d such that x, x+d, x+2d, x+4d are all square numbers?
One example would be 49,169,289,529. This is the only example I have found so far ...

**2**

votes

**0**answers

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

**4**

votes

**2**answers

255 views

### Anticoncentration of the convolution of two characteristic functions

Edit: This is a question related to my other post, stated in a much more concrete way I think.
I am interested in anything (ideas, references) related to the following problem:
Suppose that $A \...

**1**

vote

**1**answer

114 views

### A (Hard?) combinatorial optimization problem involving the representation numbers

Given a (suppose prime order) group G, for any two partions $\{A_i\}_{i\in I}$ and $\{B_j\}_{j\in J}$ of the group $G$ consider the following quantity
$$ E = \sum\limits_{i \in I,j \in J} \max_{g} r_{...

**4**

votes

**1**answer

364 views

### A problem related with 'Postage stamp problem'

A friend of mine taught me this question. I found that it is related with 'Postage stamp problem' (though it does not seem to be same).
Let $m,a_1\lt a_2\lt \cdots\lt a_n$ be natural numbers. Now let ...

**3**

votes

**3**answers

431 views

### Infinite Partitions of the Primes and Sums of Reciprocals (Revised)

I have revised my original post. The questions I asked there were not well-put or even thought through. I don't want to delete, however, since some of the comments may be of interest to other MO users....