6
votes
0answers
71 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
1answer
99 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 ...
2
votes
1answer
140 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
0answers
128 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 ...
1
vote
1answer
267 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
1answer
443 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
0answers
37 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 ...
23
votes
1answer
534 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
0answers
151 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 ...
8
votes
2answers
347 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 ...
6
votes
5answers
584 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 ...
7
votes
0answers
105 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 ...
4
votes
1answer
272 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 ...
3
votes
1answer
151 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
0answers
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 ...
4
votes
1answer
379 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 ...
8
votes
0answers
126 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$ ...
3
votes
0answers
60 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
3answers
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
0answers
82 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
1answer
461 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} ...
13
votes
3answers
722 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
1answer
515 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
1answer
507 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 ...
4
votes
1answer
338 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
2answers
270 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 ...
5
votes
0answers
134 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
1answer
302 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
1answer
192 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 ...
5
votes
3answers
511 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
0answers
305 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
1answer
294 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, ...
1
vote
1answer
172 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
1answer
253 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
0answers
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 ...
21
votes
2answers
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}$ ...
4
votes
2answers
397 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
1answer
153 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 ...
13
votes
1answer
642 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 ...
1
vote
1answer
311 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 ...
4
votes
3answers
476 views

Selecting $k$ integers from an interval $[0, N]$ to maximize the minimum difference between pairwise sums

I have an optimization problem where I need to select $k$ integers over the interval $[0, N]$ s.t. I maximize the minimum difference between any pairwise sum of the $k$ integers (where we also include ...
18
votes
0answers
357 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 ...
1
vote
1answer
329 views

Generalizations of Cauchy-Davenport Theorem

The Cauchy-Davenport Theorem says that if $A_1, \ldots, A_k$ are subsets of ${\mathbb Z}_p$, $p$ prime, then $| \sum_i A_i | \geq \min (p, \sum_i |A_i| -k +1)$. I am looking for a generalization that ...
6
votes
1answer
247 views

Recovering Sidon sets from difference sets, part 2.

This is inspired by a recent question. A set $A \subset \mathbb{Z}/n\mathbb{Z}$ with $|A|=m$ is a Sidon set if all the pairwise sums of distinct elements are unequal: $A+A=\{a+a' \mid a,a' \in A, a ...
2
votes
2answers
350 views

Recovering Sidon sets from difference sets

How can I recover a Sidon set $A\subseteq \mathbb{Z}/n\mathbb{Z}$ from the set $A-A\subseteq \mathbb{Z}/n\mathbb{Z}$? Is it even unique? (up to translation and reflection) ($A-A$ stands for the set ...
23
votes
2answers
2k views

Number of elements in the set $\{1,\cdots,n\}\times\{1,\cdots,n\}$

Let $A_n=\{a\cdot b : a,b \in \mathbb{N}, a,b\leq n\}$. Are there any estimates for $|A_n|$? Will it be $o(n^2)$?
9
votes
0answers
518 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 ...
3
votes
0answers
201 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
0answers
115 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 ...
10
votes
0answers
426 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 ...