User seva - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T20:58:00Z http://mathoverflow.net/feeds/user/9924 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/130623/fano-plane-drawings-embedding-pg2-2-into-the-real-plane Fano plane drawings: embedding PG(2,2) into the real plane Seva 2013-05-14T19:20:10Z 2013-05-15T01:41:09Z <p>By a drawing of the <a href="http://en.wikipedia.org/wiki/Fano_plane" rel="nofollow">Fano plane</a> I mean a system of seven simple curves and seven points in the real plane such that</p> <ul> <li>every point lies on exactly three curves, and every curve contains exactly three points;</li> <li>there is a unique curve through every pair of points, and every two curves intersect in exactly one point;</li> <li>the curves do not intersect except in the seven points under consideration.</li> </ul> <p>The familiar picture</p> <p><img src="http://math.haifa.ac.il/~seva/MathOverflow/Fano-1.jpg" alt="Traditional Fano plane"></p> <p>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:</p> <p><img src="http://math.haifa.ac.il/~seva/MathOverflow/Fano-2.jpg" alt="Non-intersecting Fano plane"></p> <p>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:</p> <blockquote> <p>Is every drawing of the Fano plane degenerate?</p> </blockquote> <p>(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.)</p> http://mathoverflow.net/questions/128056/additive-combinatorics-reference-request/128068#128068 Answer by Seva for Additive Combinatorics - reference request Seva 2013-04-19T11:15:00Z 2013-04-19T11:15:00Z <p>For a somewhat similar argument, see Proposition 2.5 from Alon's 1987 paper Subset sums", available <a href="http://www.tau.ac.il/~nogaa/PDFS/Publications/Subset%20sums.pdf" rel="nofollow">here</a>. </p> http://mathoverflow.net/questions/127499/perimeter-neighborhood-of-a-graph-on-grid/127555#127555 Answer by Seva for Perimeter/Neighborhood of a graph on grid Seva 2013-04-14T19:29:39Z 2013-04-14T19:29:39Z <p>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.</p> <p>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 <code>$0&lt;x_i&lt;k$</code>, and, similarly, denote by $b$ the number of those $i\in[1,k]$ with <code>$0&lt;y_i&lt;k$</code>. 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$.</p> <p>For every $i\in[1,k]$ with <code>$0&lt;x_i&lt;k$</code>, 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 <code>$$\max \{ Y-\eta, a \}$$</code> horizontal edges in $\partial(V_1)$. Counting in the same way vertical edges, we get <code>\begin{align*} |\partial(V_1)| &amp;\ge \max \{ Y-\eta, a \} + \max \{ X-\xi, b \} \\ &amp;\ge \frac12\,(X-\xi+a) + \frac12\,(Y-\eta+b). \end{align*}</code></p> <p>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.</p> <p>We observe that (2) is immediate if <code>$X=k$</code> and <code>$\xi=0$</code>, and also if <code>$X&lt;k$</code> and <code>$\xi&gt;0$</code> (when <code>$a=k$</code>). The two remaining cases can be dealt with as follows.</p> <p>If <code>$X&lt;k$</code> and <code>$\xi=0$</code>, then $a$ is the number of those indices <code>$i\in[1,k]$</code> with <code>$x_i&gt;0$</code>. Therefore, in view of (1), we have $k^2/4\le aX$, whence $$X-\xi+a = X+a \ge k,$$ as wanted.</p> <p>Finally, if <code>$X=k$</code> and <code>$\xi&gt;0$</code>, then $a$ is the number of those <code>$i\in[1,k]$</code> with <code>$x_i&lt;k$</code>. Hence, (1) gives $$k^2/4 \ge a\xi+(k-a)k = k^2 - a(k-\xi),$$ implying <code>$a(k-\xi)&gt;k^2/4$</code> and, as a result, $$X-\xi+a = a+(k-\xi) > k.$$</p> http://mathoverflow.net/questions/125251/more-expanders More expanders? Seva 2013-03-22T08:40:26Z 2013-03-25T10:13:55Z <p>Having received several exhausting answers to <a href="http://mathoverflow.net/questions/124708/an-expander-graph" rel="nofollow">my recent question</a> about the expansion properties of a certain graph, I now wonder whether anything is known on the following graphs of a similar nature:</p> <p>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$.</p> <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)$.</p> <p>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$.</p> <p>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 <a href="http://mathoverflow.net/questions/124708/an-expander-graph" rel="nofollow">my original question</a> concerned with?</p> http://mathoverflow.net/questions/124708/an-expander-graph An expander (?) graph Seva 2013-03-16T17:36:12Z 2013-03-16T18:42:30Z <p>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!</p> http://mathoverflow.net/questions/123744/formal-writing-numbers-under-10/123775#123775 Answer by Seva for Formal writing: numbers under 10 Seva 2013-03-06T15:43:54Z 2013-03-06T15:43:54Z <p>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 <strong>all</strong> fit this rule. As one more example: "There are five theorems in the manuscript labeled Theorem 5".</p> http://mathoverflow.net/questions/118135/covering-all-but-k-points-with-affine-subspaces Covering all, but $k$ points with affine subspaces Seva 2013-01-05T15:55:09Z 2013-01-05T20:59:38Z <p>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$?</p> <p>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. </p> <p>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.</p> <p>What is the answer in the general case? Has it ever been studied?</p> http://mathoverflow.net/questions/117071/bipartiteness-criterion Bipartiteness criterion Seva 2012-12-23T07:41:01Z 2012-12-26T11:45:19Z <p>A graph is bipartite if and only if it does not contain odd cycles. Is there a similar criterion for <em>hypergraphs</em>? (A hypergraph is called bipartite if its vertices can be colored in two colors so that no hyperedge is monochromatic.)</p> <p>My guess is that the answer is "no" but, maybe, there are results in this direction I am not aware of. Thanks!</p> http://mathoverflow.net/questions/117121/lower-bound-for-exponential-sums/117132#117132 Answer by Seva for Lower bound for exponential sums. Seva 2012-12-24T08:15:21Z 2012-12-24T08:15:21Z <p>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}$.</p> http://mathoverflow.net/questions/108567/a-delicate-elementary-inequality A delicate elementary inequality Seva 2012-10-01T18:54:43Z 2012-12-03T15:38:26Z <p>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.</p> <p>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 <code>$$G(x,y,z) := \begin{cases} \xi\eta &amp;\ \text{if}\ \zeta\ge \xi+\eta, \\ \xi\eta-\frac14\,(\xi+\eta-\zeta)^2 &amp;\ \text{if}\ \zeta\le \xi+\eta. \end{cases}$$</code> 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 <code>\begin{align*} f(x_0,x_1,y_0,y_1) &amp;:= \min \{ 0.15s^2, x_0y_0+x_1y_1 \} \\ &amp;\qquad + G(x_0,y_1,1-s) + G(x_1,y_0,1-s) \\ &amp;\qquad + 0.25(1-s)^2, \end{align*}</code> where for brevity I write $s=x_0+x_1+y_0+y_1$, and let <code>$$\Omega := \{ (x_0,x_1,y_0,y_1)\in{\mathbb R}_{\ge 0}^4\colon 1/2 \le s \le 1. \}.$$</code> All we want to show is that $$\max_\Omega f \le 0.15.$$ (Indeed, the maximum is actually <em>equal</em> to $0.15$: say, we have $f(0.5,0,0.5,0)=0.15$.)</p> <hr> <p>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$. </p> <p><img src="http://math.haifa.ac.il/~seva/MathOverflow/x0x1y0y1.jpg" alt="The graph"></p> <p>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$. </p> http://mathoverflow.net/questions/108567/a-delicate-elementary-inequality/115291#115291 Answer by Seva for A delicate elementary inequality Seva 2012-12-03T13:34:47Z 2012-12-03T15:38:26Z <p>The paper where the inequality in question emerged is, finally, written (and uploaded to the <a href="http://arxiv.org/abs/1211.6567" rel="nofollow">arXiv</a>, 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.</p> <p>We start with the identity <code>\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*}</code> 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$.</p> <p>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}$$</p> <p>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 &amp;\ge y_1+(1-s), \tag{4} \newline y_0 &amp;\ge x_1+(1-s), \tag{5} \end{align*} and $$3(x_0+y_0)+(x_1+y_1) \ge 2. \tag{6}$$</p> <p>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.</p> <p>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, <code>\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*}</code> 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.</p> http://mathoverflow.net/questions/111576/quadratic-farkas-lemma Quadratic Farkas' Lemma? Seva 2012-11-05T20:13:23Z 2012-11-06T22:42:36Z <p>The <a href="http://en.wikipedia.org/wiki/Farkas%27_lemma" rel="nofollow">Farkas Lemma</a> 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:</p> <blockquote> <p>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$.</p> </blockquote> <p>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$:</p> <blockquote> <p>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$?</p> </blockquote> <p>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).</p> <p>I would expect that this is either false, or should be known. Can anybody construct a counterexample or suggest a reference?</p> http://mathoverflow.net/questions/109737/bounding-the-minimal-maximum-norm-of-a-solution-of-a-linear-system/109741#109741 Answer by Seva for Bounding the minimal maximum norm of a solution of a linear system. Seva 2012-10-15T18:06:40Z 2012-10-15T18:06:40Z <p>I believe you cannot give any general bound, but if the coefficients are integers, this is <a href="http://en.wikipedia.org/wiki/Siegel%27s_lemma" rel="nofollow">Siegel's Lemma</a>: a system of $M$ equations in $N$ variables with integer coefficients $b_{ij}$ has an integer solution $X$ with <code>$\|X\|_\infty \le (NB)^{M/(N-M)}$</code>, where <code>$B=\|b_{ij}\|_\infty$</code>.</p> http://mathoverflow.net/questions/63589/the-first-eigenvalue-of-a-graph-what-does-it-reflect The first eigenvalue of a graph - what does it reflect? Seva 2011-05-01T08:22:07Z 2012-10-15T13:40:33Z <p>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 <code>$\lambda_{\max}$</code> satisfies <code>$$\sqrt{\|d_U\|_2\|d_V\|_2} \le \lambda_{\max} \le \sqrt{\|d_U\|_\infty\|d_V\|_\infty};$$</code> in particular, if the graph is <code>$(r_U,r_V)$</code>-regular, then <code>$\lambda_{\max}=\sqrt{r_Ur_V}$</code>. (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,</p> <blockquote> <p>What properties of a (bipartite) graph can be read from its largest eigenvalue?</p> </blockquote> <hr> <h3>A brief summary and common reply to all those who have answered so far.</h3> <ol> <li><p>Thanks for your interest and care!</p></li> <li><p>To make it very clear: I am interested in the <em>usual</em>, not <em>Laplacian</em> eigenvalues.</p></li> <li><p>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.</p></li> <li><p>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. </p></li> <li><p>I still could not find a reference to the displayed inequality above. (@kimball: Lovasz does not have it.) </p></li> </ol> http://mathoverflow.net/questions/109504/additive-set-with-small-sum-set-and-large-difference-set/109524#109524 Answer by Seva for Additive set with small sum set and large difference set Seva 2012-10-13T11:05:37Z 2012-10-13T12:23:09Z <p>A great work on this has been done by Imre Ruzsa; see, for instance, his paper <a href="http://www.ams.org/mathscinet/search/publdoc.html?arg3=&amp;co4=AND&amp;co5=AND&amp;co6=AND&amp;co7=AND&amp;dr=all&amp;pg4=AUCN&amp;pg5=TI&amp;pg6=PC&amp;pg7=ALLF&amp;pg8=ET&amp;review_format=html&amp;s4=Ruzsa%2C%20I%2A&amp;s5=Sums%20and%20differences&amp;s6=&amp;s7=&amp;s8=All&amp;vfpref=html&amp;yearRangeFirst=&amp;yearRangeSecond=&amp;yrop=eq&amp;r=1&amp;mx-pid=2567492" rel="nofollow">"Many differences, few sums"</a> in <em>Ann. Univ. Sci. Budapest. Eötvös Sect. Math.</em> <strong>51</strong> (2008), 27–38 (2009).</p> <p>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.</p> <hr> <p>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&lt;\beta$, then $|A-A|$ is much larger than $|2A|$ (for $k$ large).</p> http://mathoverflow.net/questions/107545/cliques-in-the-paley-graph-and-a-problem-of-sarkozy Cliques in the Paley graph and a problem of Sarkozy Seva 2012-09-19T09:44:41Z 2012-09-21T05:42:00Z <p>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.</p> <p>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 <a href="http://mathoverflow.net/questions/48591/cliques-paley-graphs-and-quadratic-residues" rel="nofollow">here</a>). Notice that, letting <code>${\mathcal Q}:=\{x^2\colon x\in{\mathbb F}_p\}$</code>, one can write the assumption as $A-A\subset{\mathcal Q}$.</p> <p>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 <code>$A,B\subset{\mathbb F}_p$</code> and <code>$\min\{|A|,|B|\}\ge 2$</code>. The conjectural answer is, of course, negative, provided that $p$ is sufficiently large.</p> <p>Both problems just mentioned seem to be quite tough; but, maybe, the following combination of the two is more tractable:</p> <blockquote> <p>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}$?</p> </blockquote> <p>Compared to the first of the two aforementioned problems, we now assume that <em>every quadratic residue</em> 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?</p> <p>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, <a href="http://mathoverflow.net/users/18739/peter-mueller" rel="nofollow">Peter Mueller</a> has verified computationally that no other exceptions of this sort occur for $p&lt;1000$.) </p> http://mathoverflow.net/questions/106873/there-exists-b-subset-a-b-log-n-a-cap-2b-emptyset/107038#107038 Answer by Seva for There exists B subset A, |B| = log n, A \cap 2*B = \emptyset Seva 2012-09-12T19:56:20Z 2012-09-12T19:56:20Z <p>It seems that this was established by D.A. Klarner, although the proof has not been published till a <a href="http://plms.oxfordjournals.org/content/s3-23/4/629" rel="nofollow">year 1971 paper</a> by Choi (who credited Klarner for it). The argument is rather straightforward and does not use the probabilistic method; it goes as follows.</p> <p>For each $b\in A$, let <code>$S(b):=\{a\in A\setminus\{b\}\colon b+a\in A\}$</code>; 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 <code>$A\setminus(S(b_1)\cup\dotsb\cup S(b_{m-1})\cup\{b_1,\ldots,b_{m-1}\})$</code> with $S(b_m)$ of the smallest possible size.</p> <p>For brevity, write <code>$S:=S(b_1)\cup\dotsb\cup S(b_{m-1})\cup\{b_1,\ldots,b_{m-1}\}$</code>. 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, <code>$$|S(b_m)| \le |S(b_1)|+\dotsb+|S(b_{m-1})| + m-1.$$</code> A simple induction now confirms that $|S(b_m)|&lt;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 <code>$B=\{b_1,\ldots,b_m\}$</code> such that $m>\log_2|A|$.</p> http://mathoverflow.net/questions/102751/a-mixing-property-for-finite-fields-of-characteristic-2 A mixing property for finite fields of characteristic $2$ Seva 2012-07-20T16:54:08Z 2012-08-07T19:38:09Z <p>In connection with <a href="http://mathoverflow.net/questions/102725/a-mixing-property-of-linear-map-over-finite-fields" rel="nofollow">this MO post</a>, here is a question somewhat implicitly contained in a <a href="http://arxiv.org/pdf/1003.3736.pdf" rel="nofollow">joint paper of S. Kopparty, S. Saraf, M. Sudan, and myself</a>.</p> <p>Let ${\mathbb F}$ be a finite field, and suppose that <code>$\varphi_0\colon{\mathbb F}\mapsto{\mathbb F}$</code> is a function from <code>${\mathbb F}$</code> to itself. For each <code>$a\in{\mathbb F}$</code>, consider the function <code>$\varphi_a\colon{\mathbb F}\mapsto{\mathbb F}$</code> defined by <code>$\varphi_a(x)=\varphi_0(x)+ax$</code> (<code>$x\in{\mathbb F}$</code>).</p> <blockquote> <p>Is it true that if <code>$q:=|{\mathbb F}|$</code> is <em>even</em>, then there exists <code>$a\in{\mathbb F}$</code> such that the image of $\varphi_a$ has size larger than $2q/3$?</p> </blockquote> <p>(A negative answer would yield an improvement on the known bounds for the smallest size of a Kakeya set in the vector spaces <code>${\mathbb F}^n$</code>.)</p> <hr> <p>It may be worth explaining where the coefficient $2/3$ comes from. In <a href="http://arxiv.org/pdf/1003.3736.pdf" rel="nofollow">the aforementioned paper</a>, we show that if $q$ is an even power of $2$, then for $\varphi_0(x)=x^3$ one has <code>$\max_a |\varphi_a({\mathbb F})|\le(2q+1)/3$</code>, whereas if $q$ is an odd power of $2$, then for $\varphi_0(x)=x^{q-2}+x^2$ one has <code>$\max_a |\varphi_a({\mathbb F})|\le2(q+\sqrt q+1)/3$</code>. The question is whether one can get better bounds for an appropriate choice of the function $\varphi_0$.</p> http://mathoverflow.net/questions/64099/the-maximum-of-a-polynomial-on-the-unit-circle The maximum of a polynomial on the unit circle Seva 2011-05-06T09:17:32Z 2012-08-04T17:13:04Z <p>Encouraged by the progress made in a <a href="http://mathoverflow.net/questions/63525" rel="nofollow">recently posted MO problem</a>, here is a "conceptually related" problem originating from <a href="http://www.math.haifa.ac.il/~seva/Papers/polymax.dvi" rel="nofollow">a 2003 joint paper</a> of Sergei Konyagin and myself. </p> <p>Suppose we are given $n$ points <code>$z_1,...,z_n$</code> on the unit circle <code>$U=\{z\colon |z|=1\}$</code> and $n$ weights <code>$p_1,...,p_n\ge 0$</code> such that <code>$p_1+....+p_n=n$</code>, and we want to find yet another point <code>$z\in U$</code> to maximize the product <code>$$\prod_{i=1}^n |z-z_i|^{p_i}.$$</code> How large can we make this product by the optimal choice of $z$?</p> <blockquote> <p><strong>Conjecture.</strong> For any given <code>$z_1,...,z_n\in U$</code> and <code>$p_1,...,p_n\ge 0$</code> with <code>$p_1+...+p_n=n$</code>, there exists <code>$z\in U$</code> with <code>$$\prod_{i=1}^n |z-z_i|^{p_i} \ge 2.$$</code></p> </blockquote> <p>Here are some comments. </p> <ul> <li><p>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$.</p></li> <li><p><a href="http://www.math.haifa.ac.il/~seva/Papers/polymax.dvi" rel="nofollow">We were able to resolve</a> 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$.</p></li> <li><p>The case $n=2$ is almost trivial, but already the case $n=3$ is wide open.</p></li> <li><p>In the general case we have shown that the maximum is larger than some absolute constant exceeding $1$.</p></li> <li><p>Although this is not obvious at first glance, this conjecture is actually about the maxima of polynomials on the unit circle. </p></li> </ul> <p>I would be very interested to see any further progress!</p> http://mathoverflow.net/questions/103787/generalized-tic-tac-toe/103793#103793 Answer by Seva for Generalized tic-tac-toe Seva 2012-08-02T15:14:26Z 2012-08-02T15:14:26Z <p>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: <em>Combinatorial Games: Tic-Tac-Toe Theory</em> and <em>Foundations of Positional Games</em>, both by J. Beck.</p> http://mathoverflow.net/questions/102725/a-mixing-property-of-linear-map-over-finite-fields/102745#102745 Answer by Seva for A mixing property of linear map over finite fields Seva 2012-07-20T15:26:22Z 2012-07-20T15:26:22Z <p>Lemma 21 from a <a href="http://arxiv.org/pdf/1003.3736.pdf" rel="nofollow">joint paper of S. Kopparty, S. Saraf, M. Sudan, and myself</a> 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. </p> http://mathoverflow.net/questions/99893/can-you-cover-the-boolean-cube-0-1n-with-o1-hamming-balls-each-of-radius-n-2/102340#102340 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)? Seva 2012-07-16T10:21:09Z 2012-07-16T10:21:09Z <p>Striped out of the coding-theory notation, Theorem 12.5.10 of "Covering Codes" by Cohen, Honkala, Litsyn, and Lobstein reads as follows:</p> <blockquote> <p>If every element of <code>${\mathbb F}_2^n$</code> is at most Hamming distance $r$ away from an element of a set <code>$A\subset{\mathbb F}_2^n$</code>, then <code>$$r\ge n/2-12\sqrt{|A|}.$$</code></p> </blockquote> <p>(A remark on page 352 indicates that this theorem originates from a year 1986 paper of Lovasz, Spencer, and Vesztergombi.) </p> <p>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 <code>$(c^2/144)n=\Omega(n)$</code> balls.</p> http://mathoverflow.net/questions/101567/the-chromatic-number-of-a-hamming-related-graph The chromatic number of a Hamming-related graph Seva 2012-07-07T09:53:28Z 2012-07-07T17:09:29Z <p>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?</p> <p>Assuming for simplicity that $k$ is even, the <a href="http://en.wikipedia.org/wiki/Kneser_graph" rel="nofollow">Kneser graph</a> <code>$G_{n,k/2+1}$</code> is a subgraph of ${\overline H}_n^k$. As a result, <code>$$\chi({\overline H}_n^k) \ge \chi(G_{n,k/2+1})=n-k.$$</code> 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 <a href="http://mathoverflow.net/questions/99893/can-you-cover-the-boolean-cube-0-1n-with-o1-hamming-balls-each-of-radius-n-2/99906#99906" rel="nofollow">this MO post</a>).</p> http://mathoverflow.net/questions/100082/covering-a-hypercube-with-lines/100216#100216 Answer by Seva for Covering a (hyper)cube with lines Seva 2012-06-21T08:33:17Z 2012-06-21T08:33:17Z <p>Not an answer, but a comment too long to fit the space.</p> <p>You may be interested to know that for finite projective geometries, the property in question has a dedicated name: namely, a set <code>$A\subset PG(r,q)$</code> is called <em>$\rho$-saturating</em>, 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 <code>$A\subset{\mathbb F}_q^r$</code> given that every point of <code>${\mathbb F}_q^r$</code> is on a line through two points of $A$?</p> http://mathoverflow.net/questions/94625/the-digit-sum-snasnb The digit sum: $s(na)=s(nb)$ Seva 2012-04-20T11:23:35Z 2012-06-17T19:16:19Z <p>Not that I was serious about the following question, but I think it is a must-to-ask as a follow-up to <a href="http://mathoverflow.net/questions/94525/equal-digit-sums" rel="nofollow">this MO post</a>. </p> <p>For integer $n\ge0$, let $s(n)$ denote the sum of the digits in the decimal representation of $n$.</p> <blockquote> <p>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? </p> </blockquote> http://mathoverflow.net/questions/99178/erdos-szekeres-theorems/99189#99189 Answer by Seva for Erdos-Szekeres Theorems Seva 2012-06-09T19:38:35Z 2012-06-09T19:38:35Z <p>Firstly, I second Qiaochu's remark that I've never heard the Ramsey theorem referred to as Erdős-Szekeres' theorem. </p> <p>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 <code>$\{a_1,...,a_n\}$</code>, consider the complete graph on the vertex set $[n]$, coloring the edge $(i,j)$ with <code>$1\le i&lt;j\le n$</code> <em>blue</em> if $a_i\le a_j$, and <em>red</em> 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.</p> http://mathoverflow.net/questions/98343/number-of-integers-coprime-to-l/98357#98357 Answer by Seva for Number of integers coprime to l Seva 2012-05-30T10:31:05Z 2012-05-31T17:20:41Z <p>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 <code>$$R = \sum_{d\mid l} \mu(d) \{x/d\}.$$</code> 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 <code>$\{x/d\}$</code> and estimate the resulting sums.</p> <hr> <p>As to the paper you mention, I think I was able to spot it out: is it "Extremal values of <code>$\Delta(x,N)=\sum_{n&lt;xN,(n,N)=1} 1-x\phi(N)$</code>" by P. Codeca and M. Nair, published in <em>Canad. Math. Bull.</em> <strong>41</strong> (3) (1998), pp. 335–347? Another paper by the same authors on the same subject: "Links between <code>$\Delta(x,N)=\sum_{n&lt;xN,(n,N)=1} 1-x\phi(N)$</code> and character sums", <em>Boll. Unione Mat. Ital. Sez. B Artic. Ric. Mat.</em> <strong>6</strong> (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, <em>Canad. J. Math.</em> <strong>7</strong> (1955), pp. 347–357.</p> http://mathoverflow.net/questions/94436/chebyshevs-theorem/95804#95804 Answer by Seva for Chebyshev's Theorem Seva 2012-05-02T19:19:19Z 2012-05-02T19:19:19Z <p>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 <a href="http://en.wikipedia.org/wiki/Kronecker%27s_theorem#A_result_in_diophantine_approximation" rel="nofollow">this Wikipedia article</a>.</p> http://mathoverflow.net/questions/94827/the-second-moment-of-a-sum-of-floor-functions/94852#94852 Answer by Seva for The Second Moment of a Sum of Floor Functions Seva 2012-04-22T15:50:49Z 2012-04-23T07:36:30Z <p>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 <code>$\{x\}$</code>, you can write your sum as <code>$$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).$$</code></p> <p>If you need more precision, you have to find the main term of the sum <code>$\sum_d d^{-1}\{d^{-1}n\}$</code>. 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. </p> <hr> <p>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 <code>$\sum_{k=1}^n \tau(k)$</code> 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 <code>$$S = 2 \sum_{dx\le n} x - \sum_{k=1}^n \tau(k).$$</code><br> Letting $k=dx$, we get <code>$$S = 2 \sum_{k=1}^n \sigma(k) - \sum_{k=1}^n \tau(k),$$</code> where $\sigma$ is the sum-of-divisors function. This gives you an identity containing arithmetic functions'', as you requested.</p> http://mathoverflow.net/questions/93744/estimating-a-partial-sum-of-weighted-binomial-coefficients/93749#93749 Answer by Seva for Estimating a partial sum of weighted binomial coefficients Seva 2012-04-11T10:22:50Z 2012-04-11T16:34:12Z <p>Sums of this sort are estimated by their largest summand, and the resulting estimate will depend on the relation between $\alpha$ and $\lambda$.</p> <p>The ratio of the $(k+1)$th and the $k$th terms of the <em>untruncated</em> sum is <code>$$\lambda \frac{n-k}{k+1},$$</code> showing that the sequence of summands is unimodal, with the maximum value attained for $k$ about <code>$\frac{\lambda}{\lambda+1}\,n$</code>. Consequently, if $\alpha&lt;\lambda/(\lambda+1)$, then your sum is between <code>$\binom n{\lfloor\alpha n\rfloor}\lambda^{\lfloor\alpha n\rfloor}$</code> and <code>$n\binom n{\lfloor\alpha n\rfloor}\lambda^{\lfloor\alpha n\rfloor}$</code>, which is $2^{H((\alpha)+\alpha\log_2\lambda+o(1))n}$; similarly, if <code>$\alpha&gt;\lambda/(\lambda+1)$</code>, then the sum is <code>$2^{(H(\lambda/(\lambda+1))+(\lambda/(\lambda+1))\log_2\lambda+o(1))n}=(\lambda+1)^{1+o(1)}$</code>. (Both estimates assume that $\alpha$ and $\lambda$ are fixed, and $n\to\infty$.)</p> http://mathoverflow.net/questions/130623/fano-plane-drawings-embedding-pg2-2-into-the-real-plane Comment by Seva Seva 2013-05-17T18:22:04Z 2013-05-17T18:22:04Z Hm-m-m... I'd say you <i>do</i> 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. http://mathoverflow.net/questions/130623/fano-plane-drawings-embedding-pg2-2-into-the-real-plane Comment by Seva Seva 2013-05-16T08:57:40Z 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. http://mathoverflow.net/questions/130623/fano-plane-drawings-embedding-pg2-2-into-the-real-plane/130648#130648 Comment by Seva Seva 2013-05-15T06:06:39Z 2013-05-15T06:06:39Z Seems it does - very nice! http://mathoverflow.net/questions/130284/bounding-number-of-solutions-to-an-equation Comment by Seva Seva 2013-05-10T18:54:16Z 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. http://mathoverflow.net/questions/128056/additive-combinatorics-reference-request/128068#128068 Comment by Seva Seva 2013-04-19T11:50:47Z 2013-04-19T11:50:47Z Not that I could recall it, at least... http://mathoverflow.net/questions/125251/more-expanders/125418#125418 Comment by Seva Seva 2013-03-26T09:32:45Z 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 <i>two</i> 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$)? http://mathoverflow.net/questions/125251/more-expanders/125418#125418 Comment by Seva Seva 2013-03-25T10:07:34Z 2013-03-25T10:07:34Z The argument for the second graph is really nice, thanks! http://mathoverflow.net/questions/125251/more-expanders Comment by Seva Seva 2013-03-22T20:16:05Z 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? http://mathoverflow.net/questions/125251/more-expanders Comment by Seva Seva 2013-03-22T18:46:46Z 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? :-) ) http://mathoverflow.net/questions/125251/more-expanders Comment by Seva Seva 2013-03-22T17:51:01Z 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. http://mathoverflow.net/questions/124708/an-expander-graph/124714#124714 Comment by Seva Seva 2013-03-17T07:38:54Z 2013-03-17T07:38:54Z Sorry for being unable to accept both answers... Thanks, anyway! http://mathoverflow.net/questions/123024/convergence-of-the-series-sum1-n-sin1-n Comment by Seva Seva 2013-02-26T20:00:18Z 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$?) http://mathoverflow.net/questions/122202/nonnegative-fourier-transform Comment by Seva Seva 2013-02-18T18:02:45Z 2013-02-18T18:02:45Z What do you call &quot;the other inequality&quot; and where your question originates from? http://mathoverflow.net/questions/121970/how-to-show-this-or-any-counter-example Comment by Seva Seva 2013-02-16T07:28:01Z 2013-02-16T07:28:01Z As stated, this question does not make much sense since the assumption $x&lt;y&lt;z&lt;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? http://mathoverflow.net/questions/121488/a-sum-involving-modn-arithmetic Comment by Seva Seva 2013-02-11T16:17:59Z 2013-02-11T16:17:59Z The sum of WHAT, and what exactly is your question?