George Shakan
  • Member for 7 years, 9 months
  • Last seen more than a month ago
  • Urbana, Il
Jean Bourgain's relatively lesser known significant contributions
11 votes

His work with Dilworth, Ford, Konyagin, and Kutzarova solved an open problem in compressed image sensing. Thanks to this blog post of Tao from 2007, we can get a feel of the general mentality before ...

View answer
Unconventional types of induction
10 votes

I have always been impressed by the following construction of graphs with arbitrarily large chromatic number and girth. The construction I will mention is due to Nesetril-Rodl, and the the first such ...

View answer
Sidon sets of $\mathbb{Z}/p\mathbb{Z}$
Accepted answer
9 votes

I am not sure of your level of knowledge of Sidon sets, but a good reference is O' Bryant's survey (see section 4.3 in particular) which contains several constructions in the integers. If you are ...

View answer
An exponential sum over squares
Accepted answer
9 votes

Actually, $|\sum_{M < n \leq N} e(x/n^2)| \sim c \sqrt{x}$, where $c \approx 0.016151690 + 0.0738060263i$. To see this, write $$\sum_{M < n \leq N} e(x/n^2) = \sum_{M < n \leq \epsilon \sqrt{...

View answer
Estimating $\sum_{p_1\cdots p_k\leq n} \frac{1}{p_1\cdots p_k}$ for various $k$
Accepted answer
7 votes

For any fixed $k \geq 1$, one has $$D_k(n) \sim \frac{x}{\log x} \frac{(\log \log x)^{k-1}}{(k-1)!}.$$ This was originally proved by Landau in 1909 using induction of $k$. For $k \ll \log \log x$, ...

View answer
Cliques, Paley graphs and quadratic residues
7 votes

This is a little late, but since this is the first thing that pops up with a google search of cliques in Paley graphs, I will mention the following: here is a result that improves the bound of $\sqrt{...

View answer
Differentiability of Fourier series
5 votes

The critical value is $a= 5/2$. Chamizo and Cordoba showed that the fractal dimension of $f(x,a)$ is $2 + \frac{1}{2}(1/2 - a), \ \ \ 1 \leq a \leq \frac52$.Thus $f(x,a)$ is not differentiable for $a ...

View answer
What is the narrowest interval I=[a,b] such that there are infinitely prime gaps of size in I?
Accepted answer
5 votes

You should find this wiki page useful. The current unconditional record is 246. Assuming Elliot Halberstam, the current record is 12, and assuming generalized Elliot Halberstam, the current record is ...

View answer
Density of Sophie Germain $3\bmod 4$ primes
Accepted answer
4 votes

As with most questions about finding primes in linear forms, nothing is known. We expect that the number of Sophie Germain primes $\leq x$ equivalent to 3 modulo 4 is $$\sim \frac{2x}{\log^2 x} \prod_{...

View answer
Dirichlet Characters as Eigenvectors
Accepted answer
4 votes

I believe the eigenvectors are the ones you guessed, but in your second example, the dimensions of some of the eigenspaces are larger than one. I would guess that Mathematica chose a basis for those ...

View answer
Uniform power-saving estimate for an exponential sum
3 votes

We set $$e_N(\theta) := e^{2 \pi I \theta/N}.$$ Your sum which is equal to $$\left|\sum_x e_N(x^2 m)\right|^2$$ and is known as a Gauss sum. Gauss himself studied these extensively. Following him, we ...

View answer
Better bounds for exact-intersection Erdős–Ko–Rado system?
3 votes

Here is a proof that $|X| \leq 4n-1$. Given your system $X$, let $\chi_1 , \ldots, \chi_N \in \mathbb{R}^{4n}$ be the characteristic vectors of the elements of $X$. Then \begin{equation*} \chi_i \...

View answer
Unique representation and sumsets
Accepted answer
1 votes

One can have $|2A|$ as small as $2|A|$. Take $A = H \cup \{g\}$ where $H$ is a subgroup, $g \notin H$ and$g \neq -g$. Then $|A+A| = 2|A| + O(1)$ while $g+H$ and $H - g$ all have a unique ...

View answer
Sum-product estimate in finite fields
1 votes

First off, we can remove the condition that $|A| \geq |F|^{\delta}$. One expects to be able to take any $\epsilon < 1$, as long as $|A| \leq |F|^{1/2}$ (not quite, see Oliver's comment below). The ...

View answer
Unbalanced version of incidences between points and unit circles
Accepted answer
1 votes

Let $I(P,C)$ be the number of incidences in your point-circle configuration. One has $$I(P,C) \ll |P|^{2/3} |C|^{2/3} + |C| + |P|,$$ by the Szemeredi-Trotter theorem. Note that while this is optimal ...

View answer
Large arithmetic progression modulo $p$
1 votes

The statement is not true. Take $B$ to be a set of the form $$\{a + b M : 1 \leq a, b \leq N\},$$ where $(N+1)M <p$, $N^2 \approx p^{1/3}$ and $n < 2M$. Then $B$ is Freiman isomorphic to the ...

View answer
Turan's theorem for connected graphs?
1 votes

First, tthere are other extremal examples than the complement of the Turan graph for $n = 3k-4$. The $3k-4$ example is given by the following. There is also an easy construction that shows that the ...

View answer
Intuition for Freiman dimension
1 votes

Seva's answer is in my opinion quite nice. I will elaborate on some other things that I have thought of to try to supplement what he has said. The Freiman dimension of an additive set, $A$, can be ...

View answer