**9**

votes

**2**answers

496 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

133 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

62 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

145 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

924 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

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

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

**3**

votes

**0**answers

89 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

508 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

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

**13**

votes

**3**answers

745 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}$?

**19**

votes

**1**answer

527 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

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

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

**5**

votes

**2**answers

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

**2**

votes

**1**answer

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

**4**

votes

**1**answer

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

**4**

votes

**3**answers

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

**4**

votes

**2**answers

277 views

### The density of numbers of the form $p + 2^k$

In 1934, Romanoff proved that the following set has positive lower density:
$$\displaystyle \mathcal{R}(x)= \{n \in \mathbb{N} : n \leq x, n = p + 2^k \}$$
where $p$ is a prime and $k \geq 0$ is a ...

**1**

vote

**1**answer

245 views

### Is $x + y \ne y+nx$ for $x \ne 0$ and $n \ge 2$ (in an ordered group)?

Let $(A, +, \preceq)$ be an ordered group, namely $(A, +)$ is a group and $\preceq$ is a total order on $A$ such that $x + z \prec y + z$ and $z + x \prec z + y$ for all $x,y,z \in A$ with $x \prec ...

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

**1**answer

332 views

### Minimal polynomial of sums of roots of unity with constant term $\pm1$

Let prime $p$ and given $\zeta_p = e^{2\pi i/p}$. It is well-known that the minimal polynomial of $x = \zeta_p + \zeta_p^{p-1}$ has a constant term either $\pm 1$ and, for certain $p$, the sum of ...

**3**

votes

**1**answer

199 views

### When does a Bohr set have the right size?

Fix a set $
\Gamma\subset \mathbb F_p$, the field with $p$ elements and a parameter $\epsilon>0$. The Bohr set $B(\Gamma,\epsilon)$ consists of those $x$ for which $x\cdot \Gamma\subseteq[-\epsilon ...

**1**

vote

**0**answers

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

**5**

votes

**3**answers

513 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

315 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

297 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

355 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

295 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

337 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

178 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

85 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

208 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

463 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

151 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

171 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

265 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

97 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

116 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

407 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

159 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

438 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

154 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

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

**13**

votes

**1**answer

708 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

143 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

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

**1**

vote

**1**answer

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