User seva - MathOverflow

Fano plane drawings: embedding PG(2,2) into the real plane

2013-05-14T19:20:10Z

By a drawing of the Fano plane I mean a system of seven simple curves and seven points in the real plane such that

every point lies on exactly three curves, and every curve contains exactly three points;
there is a unique curve through every pair of points, and every two curves intersect in exactly one point;
the curves do not intersect except in the seven points under consideration.

The familiar picture

does not count as a drawing, since the last requirement is not satisfied: there are two "illegal" intersections. In fact, this is easy to fix:

However, this drawing is degenerate in the sense that two of the curves just "touch" each other, without crossing, at some point. And here, eventually, my question goes:

Is every drawing of the Fano plane degenerate?

(Although I can give a topological definition of degeneracy, it is a little technical and, may be, not the smartest possible one, so I prefer to suppress it here.)

Answer by Seva for Additive Combinatorics - reference request

2013-04-19T11:15:00Z

For a somewhat similar argument, see Proposition 2.5 from Alon's 1987 paper ``Subset sums", available here.

Answer by Seva for Perimeter/Neighborhood of a graph on grid

2013-04-14T19:29:39Z

If you are serious about this, search the web for the "edge-isoperimetric problem for the grid graph". If you just want a (relatively) short solution to your specific problem, consider the following.

Let $k:=\sqrt n$, and assume for simplicity that $k$ is an integer and $|V_1|=n/4=k^2/4$. Let $x_1,\ldots,x_k$ and $y_1,\ldots,y_k$ be the number of points from $V_1$ on the "horizontal" and "vertical" segments of your grid, respectively. Thus, $0\le x_i,y_j\le k$, and $$ x_1+\dotsb+x_k=y_1+\dotsb+y_k=k^2/4. \tag{1} $$ Write $X:=\max x_i,\ \xi:=\min x_i,\ Y:=\max y_i$, and $\eta:=\min y_i$. Also, denote by $a$ the number of those indices $i\in[1,k]$ with $0<x_i<k$ , and, similarly, denote by $b$ the number of those $i\in[1,k]$ with $0<y_i<k$ . Finally, let $\partial(V_1)$ be the set of all those edges joining a vertex from $V_1$ with a vertex from $V_2$. We want to show that $|\partial(V_1)|\ge k$.

For every $i\in[1,k]$ with $0<x_i<k$ , the $i$th horizontal segment contributes at least one edge to $\partial(V_1)$; hence, the number of horizontal edges in $\partial(V_1)$ is at least $a$. Also, for each $i\in[1,k-1]$ the number of horizontal edges in $\partial(V_1)$ between the $i$th vertical segment and the $i+1$ vertical segment is at least $|y_{i+1}-y_i|$. Thus, the number of horizontal edges in $\partial(V_1)$ is at least $$ |y_2-y_1|+\dotsb+|y_k-y_{k-1}| \ge Y-\eta. $$ As a result, we have at least $$ \max \{ Y-\eta, a \} $$ horizontal edges in $\partial(V_1)$. Counting in the same way vertical edges, we get \begin{align*} |\partial(V_1)| &\ge \max \{ Y-\eta, a \} + \max \{ X-\xi, b \} \\ &\ge \frac12\,(X-\xi+a) + \frac12\,(Y-\eta+b). \end{align*}

We now show that $$ X-\xi+a\ge k. \tag{2} $$ Similarly, $Y-\eta+b\ge k$, and the two estimates readily yield the assertion.

We observe that (2) is immediate if $X=k$ and $\xi=0$ , and also if $X<k$ and $\xi>0$ (when $a=k$ ). The two remaining cases can be dealt with as follows.

If $X<k$ and $\xi=0$ , then $a$ is the number of those indices $i\in[1,k]$ with $x_i>0$ . Therefore, in view of (1), we have $k^2/4\le aX$, whence $$ X-\xi+a = X+a \ge k, $$ as wanted.

Finally, if $X=k$ and $\xi>0$ , then $a$ is the number of those $i\in[1,k]$ with $x_i<k$ . Hence, (1) gives $$ k^2/4 \ge a\xi+(k-a)k = k^2 - a(k-\xi), $$ implying $a(k-\xi)>k^2/4$ and, as a result, $$ X-\xi+a = a+(k-\xi) > k. $$

More expanders?

2013-03-22T08:40:26Z

Having received several exhausting answers to my recent question about the expansion properties of a certain graph, I now wonder whether anything is known on the following graphs of a similar nature:

1) The graph on ${\rm GF}(p)$ with $z$ adjacent to $-z$ and also to $gz$, where $g$ is a fixed primitive root mod $p$.

2) The graph on ${\rm GF}(2^n)$ with $z$ adjacent to $z+e$ and also to $gz$, where $e$ is a fixed non-zero element, and $g$ is a generating element of ${\rm GF}(2^n)$.

3) The graph on $({\mathbb Z}/2^n{\mathbb Z})^\times$ (odd residue classes mod $2^n$) with $z$ adjacent to $z^{-1}$ and also to $z+2$.

Are these (families of) graphs known to be good expanders? Can one investigate them using Selberg's 3/16-theorem or other "standard" tools used to study the graph my original question concerned with?

An expander (?) graph

2013-03-16T17:36:12Z

For a prime $p$, consider the graph on the vertex set ${\mathbb F}_p$, in which every vertex $z$ is adjacent to $z\pm 1$ and also to $z^{-1}$ (unless $z=0$). I was told that this graph is known to be an expander, but the person who told me this couldn't recall where exactly this graph has been studied. Does anybody know the reference? Thanks!

Answer by Seva for Formal writing: numbers under 10

2013-03-06T15:43:54Z

I believe that the rule here is to spell out numbers used for counting (unless they require three or more words to be spelled out), and use digits otherwise. Just check the examples in the answers above to see that they all fit this rule. As one more example: "There are five theorems in the manuscript labeled Theorem 5".

Covering all, but $k$ points with affine subspaces

2013-01-05T15:55:09Z

For non-negative integer $d\le n$ and $k\le 2^n$, how many affine subspaces of co-dimension $d$ are needed to cover all, but exactly $k$ elements of the vector space ${\mathbb F}_2^n$, and what are the possible values of $k$?

I know the answer in two particular cases. The case $d=1$ is about hyperplane coverings. It is not difficult to see that in this case $k$ must be a power of $2$, and for all but $k=2^s$ elements to be covered, one needs at least $n-s$ hyperplanes.

Another situation where the answer is known to me is $k=1$: by a year 1977 result of R. Jamison, to cover all but exactly one element of ${\mathbb F}_2^n$, one needs at least $n+2^d-d-1$ affine co-$d$-subspaces.

What is the answer in the general case? Has it ever been studied?

Bipartiteness criterion

2012-12-23T07:41:01Z

A graph is bipartite if and only if it does not contain odd cycles. Is there a similar criterion for hypergraphs? (A hypergraph is called bipartite if its vertices can be colored in two colors so that no hyperedge is monochromatic.)

My guess is that the answer is "no" but, maybe, there are results in this direction I am not aware of. Thanks!

Answer by Seva for Lower bound for exponential sums.

2012-12-24T08:15:21Z

This seems easier than you might have expected. Up to normalization, your quantities $\alpha(m,D)$ are Fourier coefficients of the indicator function of $D$ (for which reason many people would rather use the notation $\hat 1_D(m)$). As such, they satisfy the Parseval identity $$ \sum_m |\alpha(m,D)|^2 = n|D|. $$ In view of $|\alpha(m,D)|\le|D|$, this yields $$ n|D| \le \sum_m |D| |\alpha(m,D)|, $$ whence $$ \sigma = \frac1n \sum_m |\alpha(m,D)| \ge 1. $$ Moreover, for equality to hold, one needs all $|\alpha(m,D)|$ to be equal to either $0$ or $|D|$, which is only possible if $D$ is a coset of a subgroup of ${\mathbb Z}/n{\mathbb Z}$.

A delicate elementary inequality

2012-10-01T18:54:43Z

The following "piecewise-quadratic" inequality emerged in a joint work of Rom Pinchasi and myself. The inequality is surprisingly delicate, and all our attempts to simplify it made it false. By the end of the day, we were able to prove the inequality, but the proof is unreasonably sophisticated, totalling to about 15 pages. We would be happy to have a shorter proof.

The inequality involves the function $G$ of three real variables, defined as follows: if $(\xi,\eta,\zeta)$ is a non-decreasing rearrangement of $(x,y,z)$, then we let $$ G(x,y,z) := \begin{cases} \xi\eta &\ \text{if}\ \zeta\ge \xi+\eta, \\ \xi\eta-\frac14\,(\xi+\eta-\zeta)^2 &\ \text{if}\ \zeta\le \xi+\eta. \end{cases} $$ Thus, for instance, we have $G(9,6,7)=38$, whereas $G(7,14,6)=42$. Now consider the function $f$ of four variables defined by \begin{align*} f(x_0,x_1,y_0,y_1) &:= \min \{ 0.15s^2, x_0y_0+x_1y_1 \} \\ &\qquad + G(x_0,y_1,1-s) + G(x_1,y_0,1-s) \\ &\qquad + 0.25(1-s)^2, \end{align*} where for brevity I write $s=x_0+x_1+y_0+y_1$, and let $$ \Omega := \{ (x_0,x_1,y_0,y_1)\in{\mathbb R}_{\ge 0}^4\colon 1/2 \le s \le 1. \}. $$ All we want to show is that $$ \max_\Omega f \le 0.15. $$ (Indeed, the maximum is actually equal to $0.15$: say, we have $f(0.5,0,0.5,0)=0.15$.)

At Pat Devlin's suggestion, here is the graph of the maximum as a function of the sum $s=x_0+x_1+y_0+y_1$.

It looks nice, but does not seem to be a graph of some "simple" function; and so, there is probably no simple analytic expression for $\max f$ over all quadruples $(x_0,x_1,y_0,y_1)$ adding up to $s$.

Answer by Seva for A delicate elementary inequality

2012-12-03T13:34:47Z

The paper where the inequality in question emerged is, finally, written (and uploaded to the arXiv, in case anybody is interested). We were eventually able to simplify the proof and squeeze it down to just about six pages; indeed, the whole paper is now shorter than our original proof. I sketch very briefly the new proof below.

We start with the identity \begin{multline*} G((x+y)/2,(x+y)/2,z) = G(x,y,z) \newline + \frac14(x-y)^2 - \frac14 \big(\max\{|x-y|-z, 0 \} \big)^2. \tag{1} \end{multline*} Once stated, this is easy to verify by a careful case analysis. An immediate consequence is that $G(x,y,z)$ can only grow if both $x$ and $y$ are replaced with their average $(x+y)/2$.

As another preparation step, we exploit the internal symmetries of $f$ to assume, without loss of generality, that $$ x_0+x_1 \ge y_0+y_1 \tag{2} $$ and also $$ x_0+y_0 \ge x_1+y_1. \tag{3} $$

Our big plan is to investigate how $f$ changes under the balancing operation which includes replacing $x_0$ and $y_1$ with their average $(x_0+y_1)/2$ and, simultaneously, $x_1$ and $y_0$ with their average $(x_1+y_0)/2$. Using the identity (1), we could show that either $f$ is non-decreasing under such balancing, or, under the assumptions (2) and (3), we have \begin{align*} x_0 &\ge y_1+(1-s), \tag{4} \newline y_0 &\ge x_1+(1-s), \tag{5} \end{align*} and $$ 3(x_0+y_0)+(x_1+y_1) \ge 2. \tag{6} $$

The precise meaning of being non-decreasing under balancing is that $$ f(x_0,x_1,y_0,y_1) \le f(z_0,z_1,z_1,z_0), $$ where $z_0=(x_0+y_1)/2$ and $z_1=(x_1+y_0)/2$. Consequently, in this case the problem reduces to maximizing a function of just two variables, which is a feasible task.

Now, if $f$ is decreasing under balancing, then, in view of (4) and (5) and by the definition of the function $G$, we have $$ G(x_0,y_1,1-s) = y_1(1-s) \ \text{and}\ G(x_1,y_0,1-s)=x_1(1-s). $$ Hence, \begin{multline*} f(x_0,x_1,y_0,y_1) = \min\{0.15s^2,x_0y_0+x_1y_1\} \newline + (x_1+y_1)(1-s) + 0.25(1-s)^2. \end{multline*} The expression in the right-hand side is can only increase if $x_0$ and $y_0$ are both replaced with their average, and, simultaneously, $x_1$ and $y_1$ are replaced with their average. Consequently, we can assume that $x_0=y_0$ and $x_1=y_1$. This, again, reduces the problem to maximizing a function of two variables, which takes some two more pages to accomplish.

Quadratic Farkas' Lemma?

2012-11-05T20:13:23Z

The Farkas Lemma says that if a system of linear inequalities implies yet another linear inequality, then this last inequality can be obtained by taking a positive linear combination of the inequalities from the system. The precise statement is as follows:

Let $L_1,\dotsc,L_m$ and $P$ be linear polynomials in the $n$-dimensional real variable $x=(x_1,\dotsc,x_n)$, and suppose that the set of all those $x$ with $L_1(x)\ge 0,\dotsc,L_m(x)\ge 0$ is non-empty. If $P(x)\ge 0$ for each $x$ from this set, then there exist $c_1\ge 0,\dotsc,c_m\ge 0$ with $P\ge cL_1+\dotsb+cL_m$.

For $P$ quadratic this may fail: consider, for instance, $L_1(x)=x$, $L_2(x)=1-x$, and $P(x)=x(1-x)$. I wonder, however, whether the assertion stays true if we allow summands of the form $L_iL_j$:

Suppose that $L_1,\dotsc,L_m$ are linear, and $P$ a quadratic polynomial in the $n$-dimensional real variable $x=(x_1,\dotsc,x_n)$. Given that $P(x)\ge 0$ whenever $L_1(x)\ge 0,\ldots,L_m(x)\ge 0$ (and the set of all such $x$ is non-empty), must there exist $c_i,c_{ij}\ge 0$ with $P\ge \sum c_iL_i+\sum c_{ij} L_iL_j$?

I was able to settle some particular cases; most notably, that where $n=1$ (one variable), and also that where $m=1$ (one constraint). Perhaps, with some effort I can also resolve the case $m=n=2$ (from which the case of $m=2$ and $n$ arbitrary will follow, if I am not mistaken).

I would expect that this is either false, or should be known. Can anybody construct a counterexample or suggest a reference?

Answer by Seva for Bounding the minimal maximum norm of a solution of a linear system.

2012-10-15T18:06:40Z

I believe you cannot give any general bound, but if the coefficients are integers, this is Siegel's Lemma: a system of $M$ equations in $N$ variables with integer coefficients $b_{ij}$ has an integer solution $X$ with $\|X\|_\infty \le (NB)^{M/(N-M)}$ , where $B=\|b_{ij}\|_\infty$ .

The first eigenvalue of a graph - what does it reflect?

2011-05-01T08:22:07Z

A big-picture question: what "physical properties" of a graph, and in particular of a bipartite graph, are encoded by its largest eigenvalue? If $U$ and $V$ are the partite sets of the graph, with the corresponding degree sequences $d_U$ and $d_V$, then it is easy to see that the largest eigenvalue $\lambda_{\max}$ satisfies $$ \sqrt{\|d_U\|_2\|d_V\|_2} \le \lambda_{\max} \le \sqrt{\|d_U\|_\infty\|d_V\|_\infty}; $$ in particular, if the graph is $(r_U,r_V)$ -regular, then $\lambda_{\max}=\sqrt{r_Ur_V}$ . (A reference, particularly for the double inequality above, will be appreciated.) In the general case, the largest eigenvalue also reflects in some way the "average degree" of a vertex - but is anything more specific known about it? To put it simply,

What properties of a (bipartite) graph can be read from its largest eigenvalue?

A brief summary and common reply to all those who have answered so far.

Thanks for your interest and care!
To make it very clear: I am interested in the usual, not Laplacian eigenvalues.
Although the largest eigenvalue is related to the average degree, for non-regular graphs this does not tell much; hence, I believe, understanding the meaning of the largest eigenvalue in terms of the "standard" properties of the graph is of certain interest.
It is true that different bipartite graphs (as $K_{1,ab}$ and $K_{a,b}$) may have the same largest eigenvalue, but, I believe, this does not mean that the largest eigenvalue cannot be suitably interpreted.
I still could not find a reference to the displayed inequality above. (@kimball: Lovasz does not have it.)

Answer by Seva for Additive set with small sum set and large difference set

2012-10-13T11:05:37Z

A great work on this has been done by Imre Ruzsa; see, for instance, his paper "Many differences, few sums" in Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 51 (2008), 27–38 (2009).

As a very brief answer to your question, you cannot have a set $A$ of cardinality $N$ with $|2A|\sim N$ and $|A-A|\sim N^2$ since if $|2A|=\alpha N$, then $$ \sqrt\alpha N \le |A-A| \le \alpha^2 N; $$ you will find this inequality in the aforementioned paper by Ruzsa.

The only way to construct sets with many differences and few sums I can think of (but perhaps, not the only one known to the mankind) is to use the tensor power trick. Start with you favorite set $A_0$ with $|2A_0|=\alpha|A_0|$ and $|A_0-A_0|=\beta|A_0|$, and consider the cartesian power $A:=A_0^k$ with a large $k$. You have $N=|A|=|A_0|^k$, $|2A|=\alpha^k N$, and $|A-A|=\beta^k N$; hence, if $A_0$ is chosen so that $\alpha<\beta$, then $|A-A|$ is much larger than $|2A|$ (for $k$ large).

Cliques in the Paley graph and a problem of Sarkozy

2012-09-19T09:44:41Z

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 difficult open problems.

The first problem is to show that if $p\equiv 1\pmod 4$ is prime, and a set $A\subset{\mathbb F}_p$ has the property that the difference of any two elements of $A$ is a square, then $A$ is "small". (Basic details can be found here). Notice that, letting ${\mathcal Q}:=\{x^2\colon x\in{\mathbb F}_p\}$ , one can write the assumption as $A-A\subset{\mathcal Q}$.

The second problem, to my knowledge first posed by Andras Sarkozy several years ago, is to determine whether the set of all squares is as a sumset; that is, whether ${\mathcal Q}=A+B$ with $A,B\subset{\mathbb F}_p$ and $\min\{|A|,|B|\}\ge 2$ . The conjectural answer is, of course, negative, provided that $p$ is sufficiently large.

Both problems just mentioned seem to be quite tough; but, maybe, the following combination of the two is more tractable:

For a prime $p\equiv 1\pmod 4$, writing ${\mathcal Q}$ for the set of all squares in ${\mathbb F}_p$, does there exist a set $A\subset{\mathbb F}_p$ such that $A-A={\mathcal Q}$?

Compared to the first of the two aforementioned problems, we now assume that every quadratic residue is representable as a difference of two elements of $A$; compared to the second problem we assume that $B=-A$. Is there a way to utilize these extra assumptions?

A funny observation is that sets $A$ with the property in question do exist for $p=5$ and also for $p=13$; however, it would be very plausible to conjecture that these values of $p$ are exceptional. (In this direction, Peter Mueller has verified computationally that no other exceptions of this sort occur for $p<1000$.)

Answer by Seva for There exists B subset A, |B| = log n, A \cap 2*B = \emptyset

2012-09-12T19:56:20Z

It seems that this was established by D.A. Klarner, although the proof has not been published till a year 1971 paper by Choi (who credited Klarner for it). The argument is rather straightforward and does not use the probabilistic method; it goes as follows.

For each $b\in A$, let $S(b):=\{a\in A\setminus\{b\}\colon b+a\in A\}$ ; we thus want to find a large subset $B\subset A$ so that for any $b\in B$, we have $S(b)\cap B=\varnothing$. We choose elements for $B$ one by one, starting with $b_1:=\max A$ and, once $b_1,\ldots,b_{m-1}$ got selected, choosing $b_m$ to be the element of $A\setminus(S(b_1)\cup\dotsb\cup S(b_{m-1})\cup\{b_1,\ldots,b_{m-1}\})$ with $S(b_m)$ of the smallest possible size.

For brevity, write $S:=S(b_1)\cup\dotsb\cup S(b_{m-1})\cup\{b_1,\ldots,b_{m-1}\}$ . Observing that if $a$ is one of the $k+1$ largest elements of $A$, then $|S(a)|\le k$, we conclude that $b_m\in A\setminus S$ can be chosen so that $|S(b_m)|\le |S|$; hence, $$ |S(b_m)| \le |S(b_1)|+\dotsb+|S(b_{m-1})| + m-1. $$ A simple induction now confirms that $|S(b_m)|<2^{m-1}$ and therefore, there is a way to choose $b_m$ as long as $2^{m-1}\le|A|$ holds. As a result, we end up with a set $B=\{b_1,\ldots,b_m\}$ such that $m>\log_2|A|$.

A mixing property for finite fields of characteristic $2$

2012-07-20T16:54:08Z

In connection with this MO post, here is a question somewhat implicitly contained in a joint paper of S. Kopparty, S. Saraf, M. Sudan, and myself.

Let ${\mathbb F}$ be a finite field, and suppose that $\varphi_0\colon{\mathbb F}\mapsto{\mathbb F}$ is a function from ${\mathbb F}$ to itself. For each $a\in{\mathbb F}$ , consider the function $\varphi_a\colon{\mathbb F}\mapsto{\mathbb F}$ defined by $\varphi_a(x)=\varphi_0(x)+ax$ ( $x\in{\mathbb F}$ ).

Is it true that if $q:=|{\mathbb F}|$ is even, then there exists $a\in{\mathbb F}$ such that the image of $\varphi_a$ has size larger than $2q/3$?

(A negative answer would yield an improvement on the known bounds for the smallest size of a Kakeya set in the vector spaces ${\mathbb F}^n$ .)

It may be worth explaining where the coefficient $2/3$ comes from. In the aforementioned paper, we show that if $q$ is an even power of $2$, then for $\varphi_0(x)=x^3$ one has $\max_a |\varphi_a({\mathbb F})|\le(2q+1)/3$ , whereas if $q$ is an odd power of $2$, then for $\varphi_0(x)=x^{q-2}+x^2$ one has $\max_a |\varphi_a({\mathbb F})|\le2(q+\sqrt q+1)/3$ . The question is whether one can get better bounds for an appropriate choice of the function $\varphi_0$.

The maximum of a polynomial on the unit circle

2011-05-06T09:17:32Z

Encouraged by the progress made in a recently posted MO problem, here is a "conceptually related" problem originating from a 2003 joint paper of Sergei Konyagin and myself.

Suppose we are given $n$ points $z_1,...,z_n$ on the unit circle $U=\{z\colon |z|=1\}$ and $n$ weights $p_1,...,p_n\ge 0$ such that $p_1+....+p_n=n$ , and we want to find yet another point $z\in U$ to maximize the product $$ \prod_{i=1}^n |z-z_i|^{p_i}. $$ How large can we make this product by the optimal choice of $z$?

Conjecture. For any given $z_1,...,z_n\in U$ and $p_1,...,p_n\ge 0$ with $p_1+...+p_n=n$ , there exists $z\in U$ with $$ \prod_{i=1}^n |z-z_i|^{p_i} \ge 2. $$

Here are some comments.

If true, the estimate of the conjecture is best possible, as evidenced by the situation where the points are equally spaced on $U$ and all weights are equal to $1$.
We were able to resolve a number of particular cases; say, that where the points $z_i$ are equally spaced on $U$, and also that where all weights are equal to $1$.
The case $n=2$ is almost trivial, but already the case $n=3$ is wide open.
In the general case we have shown that the maximum is larger than some absolute constant exceeding $1$.
Although this is not obvious at first glance, this conjecture is actually about the maxima of polynomials on the unit circle.

I would be very interested to see any further progress!

Answer by Seva for Generalized tic-tac-toe

2012-08-02T15:14:26Z

I am not sure about this particular game, but the general and well-studied framework is as follows: given a hypergraph $H$, two players take turns choosing vertices from $H$, the first player collecting a whole edge being the winner. (In your case, the vertex set is $[-n,n]$, and the edges are triples $(a,b,c)\in[-n,n]^3$ which add up to $0$.) Two references you may check: Combinatorial Games: Tic-Tac-Toe Theory and Foundations of Positional Games, both by J. Beck.

Answer by Seva for A mixing property of linear map over finite fields

2012-07-20T15:26:22Z

Lemma 21 from a joint paper of S. Kopparty, S. Saraf, M. Sudan, and myself gives exactly what you are looking for: for any prime power $q$ (including the case of $q$ even), there exists $a\in F$ with $|\phi_a(F)|>q/2$. The proof for $q$ even is very similar to that given above by Peter Mueller, the proof for $q$ odd is slightly different.

Answer by Seva for Can you cover the Boolean cube {0,1}^n with O(1) Hamming-balls each of radius n/2-c*sqrt(n)?

2012-07-16T10:21:09Z

Striped out of the coding-theory notation, Theorem 12.5.10 of "Covering Codes" by Cohen, Honkala, Litsyn, and Lobstein reads as follows:

If every element of ${\mathbb F}_2^n$ is at most Hamming distance $r$ away from an element of a set $A\subset{\mathbb F}_2^n$ , then $$ r\ge n/2-12\sqrt{|A|}. $$

(A remark on page 352 indicates that this theorem originates from a year 1986 paper of Lovasz, Spencer, and Vesztergombi.)

An immediate corollary is that in order to cover the whole space with balls of radius $r=n/2-c\sqrt n$, one needs at least $(c^2/144)n=\Omega(n)$ balls.

The chromatic number of a Hamming-related graph

2012-07-07T09:53:28Z

For integer $1\le k\le n$, let ${\overline H}_n^k$ denote the complement of the $k$-th power of the Hamming graph on the vertex set ${\mathbb F}_2^n$; that is, two vectors from ${\mathbb F}_2^n$ are adjacent in ${\overline H}_n^k$ whenever they differ in $k+1$ coordinates at least. What is the chromatic number of this graph?

Assuming for simplicity that $k$ is even, the Kneser graph $G_{n,k/2+1}$ is a subgraph of ${\overline H}_n^k$. As a result, $$ \chi({\overline H}_n^k) \ge \chi(G_{n,k/2+1})=n-k. $$ Improving upon this estimate (for $k$ close to $n$) would yield an improved bound for the number of Hamming spheres, needed to cover the whole space ${\mathbb F}_2^n$ (see this MO post).

Answer by Seva for Covering a (hyper)cube with lines

2012-06-21T08:33:17Z

Not an answer, but a comment too long to fit the space.

You may be interested to know that for finite projective geometries, the property in question has a dedicated name: namely, a set $A\subset PG(r,q)$ is called $\rho$-saturating, if every point of $PG(r,q)$ is contained in a subspace, generated by $\rho+1$ points from $A$. However, to my understanding, Not much is known about such sets, with the exception of the case where $\rho=1$ and $q=2$. It would be equally natural, of course, to consider the problem for the finite affine geometries: how small can be a set $A\subset{\mathbb F}_q^r$ given that every point of ${\mathbb F}_q^r$ is on a line through two points of $A$?

The digit sum: $s(na)=s(nb)$

2012-04-20T11:23:35Z

Not that I was serious about the following question, but I think it is a must-to-ask as a follow-up to this MO post.

For integer $n\ge0$, let $s(n)$ denote the sum of the digits in the decimal representation of $n$.

Is it true that for any integer $a,b>0$, the ratio of which is not a power of $10$, the set of all those $n\ge 0$ with $s(an)=s(bn)$ has zero density?

Answer by Seva for Erdos-Szekeres Theorems

2012-06-09T19:38:35Z

Firstly, I second Qiaochu's remark that I've never heard the Ramsey theorem referred to as Erdős-Szekeres' theorem.

Secondly, it is is true (and actually well-known) that the Ramsey theorem implies a kind of a "weak version" of the Erdős-Szekeres theorem. Namely, given an $n$-term sequence $\{a_1,...,a_n\}$ , consider the complete graph on the vertex set $[n]$, coloring the edge $(i,j)$ with $1\le i<j\le n$ blue if $a_i\le a_j$, and red if $a_i>a_j$. Now if $n>R(s,t)$, then our graph has either blue complete subgraph on $s$ vertices, corresponding to a length-$s$ increasing subsequence, or a red complete subgraph on $t$ vertices, corresponding to a length-$t$ decreasing subsequence.

Answer by Seva for Number of integers coprime to l

2012-05-30T10:31:05Z

It is easy to explain "how the Fourier analysis meshed in". Namely, using the standard notation for the Möbius function, the Euler's totient function, and the integer / fractional part functions, your sum can be written as $$ \sum_{n\le x} \sum_{d\mid(n,l)} \mu(d) = \sum_{d\mid l} \mu(d) \lfloor x/d \rfloor = x \sum_{d\mid l} \frac{\mu(d)}d + R = \frac{\phi(l)}lx + R, $$ where $$ R = \sum_{d\mid l} \mu(d) \{x/d\}. $$ As Fedor Petrov observed, this already suffices to improve the remainder term from $\phi(l)$ to $\tau(l)$ and indeed, to the number of square-free divisors of $l$, which is $2^{\omega(l)}$. To get better estimates, one can try to plug in the Fourier expansion for $\{x/d\}$ and estimate the resulting sums.

As to the paper you mention, I think I was able to spot it out: is it "Extremal values of $\Delta(x,N)=\sum_{n<xN,(n,N)=1} 1-x\phi(N)$ " by P. Codeca and M. Nair, published in Canad. Math. Bull. 41 (3) (1998), pp. 335–347? Another paper by the same authors on the same subject: "Links between $\Delta(x,N)=\sum_{n<xN,(n,N)=1} 1-x\phi(N)$ and character sums", Boll. Unione Mat. Ital. Sez. B Artic. Ric. Mat. 6 (2) (2003), pp. 509–516. I could find one more paper on this problem published in a Canadian journal: "The distribution of totatives" by D.H. Lehmer, Canad. J. Math. 7 (1955), pp. 347–357.

Answer by Seva for Chebyshev's Theorem

2012-05-02T19:19:19Z

This is a quantitative version of the one-dimensional Kronecker's approximation theorem; see Hardy and Wright's classical text "An introduction to the Theory of Numbers", Theorem 440. You can also check this Wikipedia article.

Answer by Seva for The Second Moment of a Sum of Floor Functions

2012-04-22T15:50:49Z

Sums of this sort are well known to the experts - but since none of them have answered so far, let me try. Denoting the fractional part of a real $x$ by $\{x\}$ , you can write your sum as $$ S = n^2 \sum_{d=1}^n \frac1{d^2} - 2n \sum_{d=1}^n \frac1d\left\{\frac nd\right\} + \sum_{d=1}^n \left\{\frac nd\right\}^2 = \frac{\pi^2}{6}\, n^2 + O(n\log n). $$

If you need more precision, you have to find the main term of the sum $\sum_d d^{-1}\{d^{-1}n\}$ . The standard technique here, I believe, would be to use the Fourier expansion of the fractional part function, but you'd better contact experts for details, to avoid re-inventing the wheel.

Here is a different kind of answer, depending on what you are after. Your sum counts the number of triples $d,x,y\in[1,n]$ with $xd,yd\le n$. Since there are $\sum_{k=1}^n \tau(k)$ such triples with $x=y$, splitting the sum into two part according to whether $x\ge y$ or $y\ge x$, we can write it as $$ S = 2 \sum_{dx\le n} x - \sum_{k=1}^n \tau(k). $$
Letting $k=dx$, we get $$ S = 2 \sum_{k=1}^n \sigma(k) - \sum_{k=1}^n \tau(k), $$ where $\sigma$ is the sum-of-divisors function. This gives you ``an identity containing arithmetic functions'', as you requested.

Answer by Seva for Estimating a partial sum of weighted binomial coefficients

2012-04-11T10:22:50Z

Sums of this sort are estimated by their largest summand, and the resulting estimate will depend on the relation between $\alpha$ and $\lambda$.

The ratio of the $(k+1)$th and the $k$th terms of the untruncated sum is $$ \lambda \frac{n-k}{k+1}, $$ showing that the sequence of summands is unimodal, with the maximum value attained for $k$ about $\frac{\lambda}{\lambda+1}\,n$ . Consequently, if $\alpha<\lambda/(\lambda+1)$, then your sum is between $\binom n{\lfloor\alpha n\rfloor}\lambda^{\lfloor\alpha n\rfloor}$ and $n\binom n{\lfloor\alpha n\rfloor}\lambda^{\lfloor\alpha n\rfloor}$ , which is $2^{H((\alpha)+\alpha\log_2\lambda+o(1))n}$; similarly, if $\alpha>\lambda/(\lambda+1)$ , then the sum is $2^{(H(\lambda/(\lambda+1))+(\lambda/(\lambda+1))\log_2\lambda+o(1))n}=(\lambda+1)^{1+o(1)}$ . (Both estimates assume that $\alpha$ and $\lambda$ are fixed, and $n\to\infty$.)

Comment by Seva

2013-05-17T18:22:04Z

Hm-m-m... I'd say you do use this - at least, for the real case. Let $A,B,C,O,A',B',C'$ be as in your comment. How many of the points $A',B',C'$ lie on the edges of the triangle $ABC$? An odd number, on the one hand (they are points of intersection of $OA$, $OB$, $OB$ with the edges), and an even number, on the other hand (they are points of intersection of the straight line through $A',B'$ and $C'$ with the edges) - a contradiction.

Comment by Seva

2013-05-16T08:57:40Z

@Noam: I see, the basic idea is that (1) any line not passing thorough a vertex of a triangle intersects an even number of its edges, while (2) for any triangle $ABC$, and any point $O$ not on its boundary, the three lines $OA$, $OB$, and $OC$ intersect an odd number of the edges.

Comment by Seva

2013-05-15T06:06:39Z

Seems it does - very nice!

Comment by Seva

2013-05-10T18:54:16Z

It may be useful to rewrite your equation as $au^2-bv^2=d$, where $u=2x-1$, $v=2y-1$, and $d=a+c-b$, and then factor the left-hand side.

Comment by Seva

2013-04-19T11:50:47Z

Not that I could recall it, at least...

Comment by Seva

2013-03-26T09:32:45Z

It is my understanding, by the way, that the situation changes significantly, and the argument does not work any longer, if one fixes two non-zero elements $e_1$ and $e_2$, and has every $z$ adjacent to both $z+e_1$ and $z+e_2$ (in addition to $g^{\pm1}z$)?

Comment by Seva

2013-03-25T10:07:34Z

The argument for the second graph is really nice, thanks!

Comment by Seva

2013-03-22T20:16:05Z

The union of, say, three cliques with a bridge between any pair of them has a very small diameter, but is not an expander?

Comment by Seva

2013-03-22T18:46:46Z

@Noam: sorry, do not get it. First, any (non-zero) field element is actually just a power of $g$. Second, I do not see why the diameter being logarithmic implies that the graph is an expander. (To my understanding, it does not - am I missing something? Could you expand? :-) )

Comment by Seva

2013-03-22T17:51:01Z

@Freddie Manners: concerning the first graph I mentioned - you are absolutely right, pretty stupid of me not to notice this myself. Concerning the second graph - I still don't see any obvious reason for it not to be an expander.

Comment by Seva

2013-03-17T07:38:54Z

Sorry for being unable to accept both answers... Thanks, anyway!

Comment by Seva

2013-02-26T20:00:18Z

Anyone can give you a simple proof, but my guess is, you are supposed to find one yourself. (A hint: what is the order of magnitude of $sin(x)-x$ for small $x$?)

Comment by Seva

2013-02-18T18:02:45Z

What do you call "the other inequality" and where your question originates from?

Comment by Seva

2013-02-16T07:28:01Z

As stated, this question does not make much sense since the assumption $x<y<z<1$ allows one to drastically simplify the sum of the absolute values. But, maybe, this is exactly what you are supposed to do, as a homework problem?

Comment by Seva

2013-02-11T16:17:59Z

The sum of WHAT, and what exactly is your question?