User boris bukh - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T05:10:49Z http://mathoverflow.net/feeds/user/806 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/129119/dimension-of-incomplete-matrix-over-finite-fields/129217#129217 Answer by Boris Bukh for Dimension of incomplete matrix over finite fields. Boris Bukh 2013-04-30T13:16:59Z 2013-04-30T18:42:44Z <p>It is true. Let $N=2^n$ be the dimension, and $q=p^k$ be the size of the field. Let $v_i$ be the $i$'th column vector. Define multiplication of vectors coordinate-wise, i.e., $uu'$ is vector whose $i$'th coordinate is $u_i u'_i$. Similarly, for a vector $u$ define $u^r$ be the result of raising all the elements of $u$ to $r$'th power. Note that the vectors $v_1^{q-1},\dotsc,v_N^{q-1}$ are linearly independent.</p> <p>Suppose, now that the rank of the matrix is $r$, i.e, some $r$ column vectors span the column space. Without loss, every $v_i$ is a linear combination of $v_1,\dotsc,v_r$. Let $S$ be the set of all the products of $q-1$ vectors from ${v_1,\dotsc,v_r}$ (repeations are allowed). If $$v_i=\sum_{j=1}^r \alpha_j v_j,$$ then $$v_i^{q-1}=\left(\sum_{j=1}^r \alpha_j v_j\right)^{q-1}=\sum_{j_1,\dotsc,j_{q-1}=1}^r (\alpha_{j_1}\dotsb\alpha_{j_{q-1}}) v_{j_1}\dotsb v_{j_{q-1}}$$ is a linear combination of vectors from $S$. Since $v_i^{q-1}$'s are linearly independent, we conclude that $|S|\geq N$. Since $|S|\leq r^{q-1}$, it follows that the rank is $$r\geq N^{1/(q-1)}.$$</p> <p>This argument is a variation on the proofs of Frankl–Wilson theorem, and of Ray-Chaudhuri–Wilson theorem.</p> http://mathoverflow.net/questions/129204/intersection-of-2-visibility-polygons/129208#129208 Answer by Boris Bukh for Intersection of 2 visibility polygons Boris Bukh 2013-04-30T11:53:14Z 2013-04-30T12:25:02Z <p>The answer is yes. I do not see a clean proof. Here is a proof by case-checking. Consider two points $q$ and $q'$ that are visible from both $p_1$ and $p_2$. There are several cases: </p> <p>1) Suppose four points $p_1$, $p_2$, $q$, $q'$ are in convex position, and points $p_1$, $p_2$ are opposite vertices of the convex hull. Then convex hull is completely inside the polygon, and in particular in the intersection of two visibility polygons. Thus, $q$ and $q'$ are in the same connected component. </p> <p>2) Four points $p_1$, $p_2$, $q$, $q'$ are in convex position, and points $p_1$, $p_2$ are adjacent vertices of the convex hull. Without loss, assume that the order is $p_1$, $p_2$, $q$, $q'$. Let $r$ be the intersection point of line segments $p_1q$ and $p_2q'$. Then the line segments $qr$ and $q'r$ are contained in the intersection of visibility regions.</p> <p>3) Point $q$ is in the convex hull of $p_1$, $p_2$ and $q'$. Then the nonconvex $4$-gon $p_1qp_2q'$ is in the intersection of visibility polygons, and line segment $qq'$ is completely contained in it.</p> <p>4) Point $p_1$ is in the convex hull of $p_2$, $q$ and $q'$. In that case the line segments $qp_1$ and $q'p_1$ are in both visibility polygons. Again, $q$ and $q'$ are connected.</p> http://mathoverflow.net/questions/124888/a-generalisation-of-sperner-families-union-free-families/124948#124948 Answer by Boris Bukh for A generalisation of Sperner families (union-free families) Boris Bukh 2013-03-19T11:52:33Z 2013-03-19T11:52:33Z <p>For $k=3$ case, there is a result of <a href="http://www.ams.org/mathscinet-getitem?mr=647989" rel="nofollow">Kleitman, Shearer and Sturtevant</a>, which gives a bound of $2^{0.7549 n}$ on the size of $C$. In fact they show a similar bound for a $k$-uniform family for any $k$. In a follow-up <a href="http://www.ams.org/mathscinet-getitem?mr=829076" rel="nofollow">paper by Alon</a> an explicit set family of exponential size is constructed.</p> http://mathoverflow.net/questions/123045/estimating-l1-functions-over-the-ball-with-radius-2r/124652#124652 Answer by Boris Bukh for Estimating L1 functions over the ball with radius 2r Boris Bukh 2013-03-15T20:48:28Z 2013-03-15T20:48:28Z <p>The answer is negative. Let $n=1$, $\Omega=(0,\infty)$ and $f(x)=\min\bigl(1/x^2,1\bigr)$. Let $x_i=2\cdot 4^i$ and $r_i=4^i$. Then $B(x_i,2r_i)$ contains $(0,1)$, and so $\int_{B(x_i,r_i)} |f|\geq \int_0^1 |f|=1$. Therefore, the putative function $g$ satisfies $$\int_0^\infty |g|\geq \sum_{i=1}^\infty \int_{B(x_i,r_i)} |g|\geq \sum_{i=1}^\infty \frac{1}{C}\int_{B(x_i,r_i)} |f|\geq \sum_{i=1}^\infty \frac{1}{C}=\infty.$$</p> http://mathoverflow.net/questions/43979/counting-roots-multidimensional-sturms-theorem Counting roots: multidimensional Sturm's theorem Boris Bukh 2010-10-28T14:37:14Z 2012-10-24T08:15:04Z <p><a href="http://en.wikipedia.org/wiki/Sturm%27s_theorem" rel="nofollow">Sturm's theorem</a> gives a way to compute the number of roots of a one-variable polynomial in an interval [a,b]. Is there a generalization to boxes in higher dimensions? Namely, let $P_1,\dotsc,P_n\in \mathbb{R}[X_1,\dotsc,X_n]$ be a collection of $n$ polynomials such that there are only finitely many roots of $P_1=P_2=\dotsb=P_n=0$. I want to be able to compute the number of roots in $[a,b]^n$. I do not care if the roots are counted with or without multiplicity. </p> <p>I would also be interested in upper bounds on the number of roots that is similar to <a href="http://en.wikipedia.org/wiki/Descartes%27_rule_of_signs" rel="nofollow">Descartes' rule of signs</a>. The only work in this connection that I managed to find is by <a href="http://www.ams.org/mathscinet-getitem?mr=1422527" rel="nofollow">Itenberg and Roy</a>, who postulated a conjectural extension of Descartes' rule of signs, which however later was <a href="http://www.ams.org/mathscinet-getitem?mr=1614424" rel="nofollow">shown to be false</a>.</p> http://mathoverflow.net/questions/102751/a-mixing-property-for-finite-fields-of-characteristic-2/103017#103017 Answer by Boris Bukh for A mixing property for finite fields of characteristic $2$ Boris Bukh 2012-07-24T16:08:11Z 2012-07-24T16:08:11Z <p>This is a justification of Peter Mueller's guess. Write $n=|\mathbb{F}|$ and put $m=\delta n$ where $\delta>1-1/e$ is arbitrary. Let $\phi_0$ be a random function, chosen uniformly from among all functions $\mathbb{F}\to\mathbb{F}$. For each $a$, the function $\phi_a$ is uniformly distributed. Let $X$ be the size of image of $\phi_0$. Let $p=\Pr[X>m]$. If $pn&lt;1$, then there is a choice of $\phi_0$ such the image of $\phi_a$ is at most $m$. The expected size of $X$ is $\bigl(1-1/e+o(1)\bigr)n$ since the probability that any given element is in the image of $\phi$ is $1-(1-1/n)^n$. Furtermore, if we think of throwing $n$ balls into $n$ bins as a martingale of length $n$, Azuma's inequality implies that <code>$\Pr\bigl[X-E[X]&gt;C\sqrt{n\log n}\,\bigr]&lt;n^{-C'}$</code>. Choosing $C$ large enough, we get the desired conclusion. </p> http://mathoverflow.net/questions/101696/lower-bound-of-the-size-of-a-collection-of-subsets-with-a-intersecting-property/101760#101760 Answer by Boris Bukh for Lower bound of the size of a collection of subsets with a intersecting property Boris Bukh 2012-07-09T10:00:34Z 2012-07-09T10:00:34Z <p>The two problems are equivalent. Indeed, let $\mathcal{F}$ be the family of sets of size at least $n/2+1$ such that no two sets have $n/2$ elements in common. Clearly, such an $\mathcal{F}$ cannot contain two sets $S,T$ such that $S\subset T$. If there is a set $S\in \mathcal{F}$ of size greater than $n/2+1$, then replace it by a set <code>$S'=S\setminus\{x\}$</code> where $x$ is any element of $S$. The result is the family <code>$\mathcal{F}'=\mathcal{F}\cup \{S'\}\setminus \{S\}$</code> which has the same size as $\mathcal{F}$, and satisfies the same condition. Repeat as long as there are sets of size greater than $n/2+1$.</p> http://mathoverflow.net/questions/66895/does-a-variety-contain-a-cartesian-product-of-two-curves Does a variety contain a cartesian product of two curves? Boris Bukh 2011-06-04T14:13:06Z 2012-07-05T09:12:40Z <p>We are given an affine variety $V\subset \mathbb{A}^n\times\mathbb{A}^n$, and wish to know if it contains a product of the form $C_1\times C_2$, where $C_1$ and $C_2$ are two curves in $\mathbb{A}^n$. First, is there an algorithm to decide this? Second, is it true that if $V$ is of degree $d$ and does contain a product of the form $C_1\times C_2$, then $V$ contains a product of the form $C_1\times C_2$ with $\deg C_1,\deg C_2\leq f(d,n)$, for some function $f$?</p> http://mathoverflow.net/questions/66895/does-a-variety-contain-a-cartesian-product-of-two-curves/101384#101384 Answer by Boris Bukh for Does a variety contain a cartesian product of two curves? Boris Bukh 2012-07-05T09:12:40Z 2012-07-05T09:12:40Z <p>Yes, there is such an algorithm. There is an effectively computable constant $N$ such that if $V$ contains a product $S\times T$ where $S,T$ are $N$-point sets, then $V$ contains product of two curves. It is actually true even in the semialgebraic setting. The result is Theorem 1.9 from <a href="http://arxiv.org/abs/1207.0705" rel="nofollow">http://arxiv.org/abs/1207.0705</a></p> <p>[ Apologies for answering my own question with a reference to my own paper. When I asked the question, I did not know the answer. ]</p> http://mathoverflow.net/questions/93545/ruzsa-type-inequalities-for-additive-energy/93555#93555 Answer by Boris Bukh for Ruzsa-type inequalities for additive energy Boris Bukh 2012-04-09T09:17:03Z 2012-04-09T09:27:51Z <p>1) No. Let $A=B=C$ be a set that is a union of interval <code>$\{1,\dots,N\}$</code> and $N$ random elements from <code>$\{1,\dotsc,N^2\}$</code>. Then $F(A,A)=KN$ for some constant $K$. On the other hand, $A+A$ is basically the interval <code>$\{1,\dotsc,N^2\}$</code>. So, $F(A,A+A)\approx N^2$. </p> <p>2) Example above show that it fails for $k=1$ and $l=2$ (from the context I assume that $k\cdot A$ means $k$-fold sumset $A+\dotsb+A$, not the $k$-dilate <code>$\{ka:a\in A\}$</code>. If dilates were meant, then the assertion is true, and one can deduce this from the Balog–Szemerédi–Gowers theorem).</p> <p>I want to add that there do exist Ruzsa-type inequalities for additive energy. Instead of sumsets, they involve a suitable extension of additive energy to more than two sets. See <a href="http://people.cs.uchicago.edu/~razborov/files/free_group.pdf" rel="nofollow">Razborov's paper on the product theorem in the free group</a> (in section 6), for example.</p> http://mathoverflow.net/questions/90331/careless-packing/90389#90389 Answer by Boris Bukh for Careless packing Boris Bukh 2012-03-06T18:42:37Z 2012-03-07T08:02:37Z <p>This is a rigorous justification of Johan Wästlund's intuition. Namely, I will show that if we tile a round ball $B$ of area $\pi\zeta(\alpha)$ by round balls of area $\pi/n^\alpha$ for some $1&lt;\alpha&lt;1.1716$, then we never get stuck provided we have placed enough balls already. </p> <p>For later use note that the radius of $n$'th ball is $n^{-\alpha/2}$. Suppose we have placed the first $N-1$ balls. Let $U$ be the union of them, and let $U'$ be the complement of $B$. We can place $N$'th ball iff the $N^{-\alpha/2}$-neighborhood of $U\cup U'$ does not contain all of $B$. We can bound the area of the neighborhood of $U$ by $$\sum_{n &lt; N} \pi(n^{-\alpha/2}+N^{-\alpha/2})^2=\sum_{n &lt; N} \pi(n^{-\alpha}+2n^{-\alpha/2}N^{-\alpha/2}+N^{-\alpha})=\pi(\Sigma_1+\Sigma_2+\Sigma_3).$$ We have $\Sigma_1\approx \zeta(\alpha)-\frac{N^{1-\alpha}}{\alpha-1}$, $\Sigma_2\approx 2N^{-\alpha/2} \frac{N^{1-\alpha/2}}{1-\alpha/2}=\frac{2}{1-\alpha/2}N^{1-\alpha}$ and $\Sigma_3\approx N^{1-\alpha}$. The area of the neighborhood of $U'$ is less than $2\pi\zeta(\alpha)^{1/2}N^{-\alpha/2}=o(N^{1-\alpha})$. The result follows since $$\frac{1}{\alpha-1}-\frac{2}{1-\alpha/2}-1$$ is positive for $\alpha&lt;4-2\sqrt{2}=1.17157\ldots$.</p> <p><em>Edit</em>: Actually, the argument works for any centrally symmetric convex shapes. The only thing I used about balls is that the Minkowski sum of a ball and a ball is a ball of the correct size.</p> <p><em>Edit 2</em>: It is clear that if one wants a stronger conclusion that one never gets stuck, then one needs to make explicit errors in the asymptotic estimates above. Then one can either decrease $\alpha$ to subsume those errors, or to consider the balls of area $\pi m^{-\alpha},\pi(m+1)^{-\alpha},\dotsc$ in a ball of total area $\pi\sum_{n\geq m} n^{-\alpha}$ to reduce the errors. This mirrors the suggestion of John Shier in the write-up linked above.</p> http://mathoverflow.net/questions/90128/erds-szekeres-for-first-differences/90188#90188 Answer by Boris Bukh for Erdős-Szekeres for first differences Boris Bukh 2012-03-04T10:11:37Z 2012-03-04T12:15:22Z <p>The $N(n)$ is exponential in $n$. First, I present a lower bound. The construction is recursive. Call a sequence whose first differences are monotone, <em>$1$-monotone</em>. Suppose $\mathbf{a}=a_1,\dotsc,a_M$ is a sequence that contains no $1$-monotone $N$-term subsequence. Pick an number $R$ that is larger than $\max_{i,j}(a_i-a_j)$. Then the sequence $\mathbf{b}=a_1,\dotsc,a_M,a_1+R,\dotsc,a_M+R$ contains no $1$-monotone subsequence of length $N+1$. Indeed, the subsequence cannot contain $N$ elements from the same half of $\mathbf{b}$. Hence, it must contain at least $2$ elements from each of the halves, which is impossible by the choice of $R$.</p> <p>The upper bound is also recursive. We will find a monotone increasing subsequence with a stronger property that either $a_i-a_1\leq a_{i+1}-a_i$ (fast-increasing) or $a_{last}-a_i\leq a_i-a_{i-1}$ (fast-decreasing). It suffices to only work with the sequences that are monotone increasing (by losing only a square, and reversing the sequence if necessary). Let $N(I,D)$ be the length of the longest monotone sequence without a fast-increasing subsequence of length $I$, and without fast-decreasing subsequence of length $D$. I claim that $N(I,D)\leq N(I-1,D)+N(I,D-1)$ (and so $N(n,n)$ is bounded by an exponential function). Suppose $\mathbf{a}$ is a monotone increasing sequence. Let $X$ be the median of $\mathbf{a}$. The median splits $\mathbf{a}$ into two equally long sequences $\mathbf{b}$ and $\mathbf{c}$. By induction applied to $\mathbf{b}$ we can find either fast-increasing sequence of length $I-1$ or fast-decreasing sequence of length $D$. In the latter case, we are done. Else, let $\mathbf{b}'$ be the fast-increasing subsequence of $\mathbf{b}$. Similarly, there is $\mathbf{c}'$ in $\mathbf{c}$ that is fast-decreasing. If $X-a_1\leq a_{last}-X$, then the concatenation of $\mathbf{b}'$ with $a_{last}$ is the desired sequence. If $X-a_1\geq a_{last}-X$ then the concatenation of $a_1$ with $\mathbf{c}'$ is a desired subsequence.</p> http://mathoverflow.net/questions/90067/a-requst-for-clarification-of-the-analysis-of-the-moser-tardos-algorithmic-proof/90114#90114 Answer by Boris Bukh for A requst for clarification of the analysis of the Moser-Tardos algorithmic proof of the Local Lemma Boris Bukh 2012-03-03T13:28:58Z 2012-03-03T15:33:13Z <p>The reason the bound you obtain is worse than the advertised bound is that you sum over all $k$, including those $k$ for which the bound on $Q(k)$ is greater than $1$. </p> <p>Suppose $T$ is an integer-valued random variable about which we know that $\Pr[T\geq k]\leq (1-\varepsilon)^k X$. Then \begin{align*} E[T]\leq (\log X/\varepsilon) \Pr[T\geq \log X/\varepsilon] + \sum_{k\geq \log X/\varepsilon} \Pr[T\geq k] =(\log X/\varepsilon)+X\sum_{k\geq \log X/\varepsilon}(1-\varepsilon)^k \end{align*} which is $O(\log X/\varepsilon)$.</p> http://mathoverflow.net/questions/1714/best-online-mathematics-videos/86926#86926 Answer by Boris Bukh for Best online mathematics videos? Boris Bukh 2012-01-28T22:06:20Z 2012-01-28T22:06:20Z <p>As of today, the digitized tapes of CBMS Lectures on Probability Theory and Combinatorial by Michael Steele <a href="http://sms.cam.ac.uk/collection/1189351" rel="nofollow">are online</a>. I heartily recommend them — the style is informal, but educating: there are jokes, juggling lessons, speculations about the stock market, and all of these amidst beautiful mathematics.</p> http://mathoverflow.net/questions/76108/an-isoperimetric-problem-on-the-hypercube/76113#76113 Answer by Boris Bukh for An isoperimetric problem on the hypercube Boris Bukh 2011-09-22T09:00:06Z 2011-09-22T09:00:06Z <p>If $E$ consists not only of unit vectors, but also of the zero vector, then according to Alon &amp; Spencer Probabilistic method'' chapter 7, the sharp isoperimetric inequality was proved by <a href="http://www.ams.org/mathscinet-getitem?mr=200192" rel="nofollow">Harper</a>. It asserts that the Hamming ball minimizes $A+E$. In that chapter they show how to get a very good asymptotic bound for the same problem.</p> http://mathoverflow.net/questions/71129/entropy-of-the-ising-model Entropy of the Ising model Boris Bukh 2011-07-24T13:40:11Z 2011-07-25T02:13:31Z <p>Consider the standard Ising model on $[0,N]^2$ for $N$ large. By that I mean the square-lattice Ising model without external field, inside an $N$-by-$N$ square. What is its entropy for $N$ large? It must behave asymptotically as $c(\beta)N^2$ for some constant $c(\beta)$ depending on the inverse temperature $\beta$. What is $c(\beta)$? Has it been computed?</p> http://mathoverflow.net/questions/64649/lower-bounds-on-the-easier-waring-problem Lower bounds on the easier Waring problem Boris Bukh 2011-05-11T16:06:15Z 2011-05-12T14:19:24Z <p>The <em>easier Waring problem</em> asks for the least number $v=v(k)$ such that every every integer is a sum of $v$ $k$'th powers <em>with signs</em>, i.e. every $n\in \mathbb{N}$ is of the form $$n=x_1^k\pm x_2^k\pm\dotsb\pm x_v^k.$$</p> <p>The problem is easier'' because unlike the usual Waring problem (without the signs) the existence of $v(k)$ is easy --- the bound $v(k)\leq 2^{k-1}+\tfrac{1}{2}k!$ follows from the repeated differencing. Of course, the upper bounds on the usual Waring problem apply, and so fact $v(k)=O(k\log k)$.</p> <p>All the lower bounds on $v(k)$ I have seen come from the congruence considerations. For example, $v(3)\geq 4$ because we need at least four terms modulo $9$. However, if we discard the congruential obstacles is there a non-trivial lower bound? To put bluntly my question is</p> <blockquote> <p>Is there $k$ large enough so that the set <code>$\{x_1^k\pm x_2^k\pm x_3^k\pm x_4^k\pm x_5^k\}$</code>has zero density?</p> </blockquote> http://mathoverflow.net/questions/60203/is-a-sequence-of-the-following-type-uniformly-distributed-modulo-1/60213#60213 Answer by Boris Bukh for Is a sequence of the following type uniformly distributed modulo 1? Boris Bukh 2011-03-31T17:23:02Z 2011-03-31T17:23:02Z <p>$H_n$ is a asymptotic to $\log n+\gamma+O(1/n)$. This means that the values of $x_n$ for $e^k \leq n\leq e^{k+1/2}$ all fall into the same interval of length about $1/2$. The sequence is not equidistributed (the proportion of $x_n$ in that interval for $n\leq e^k$ and for $n\leq e^{k+1/2}$ differ much).</p> http://mathoverflow.net/questions/58856/advances-and-difficulties-in-effective-version-of-thue-roth-siegel-theorem/58877#58877 Answer by Boris Bukh for Advances and difficulties in effective version of Thue-Roth-Siegel Theorem Boris Bukh 2011-03-18T22:07:34Z 2011-03-18T22:07:34Z <p>There has been progress towards effective Roth's theorem. Notably, <a href="http://www.ams.org/mathscinet-getitem?mr=289418" rel="nofollow">Fel'dman</a> was first to prove an effective power saving over Liouville's bound.</p> <p>In the nutshell the source of ineffectivity comes from the following kind of argument. One obtains a sequence of positive real numbers $x_1,x_2,\dotsc,$ with the property that the product of any two distinct $x$'s is at most $1$. It immediately follows that the sequence is bounded, but of course this information does not yield any actual bound. In the Thue's proofs, one argues that no <em>two</em> rational approximation can be very good simultaneously, which is where such a sequence of $x$'s arises.</p> <p>In my opinion, a good introduction to effective methods in transcendental number theory is in the <a href="http://www.math.jussieu.fr/~miw/articles/pdf/QueensPaper52.pdf" rel="nofollow">notes</a> by <a href="http://www.math.jussieu.fr/~miw" rel="nofollow">Waldschmidt</a>.</p> http://mathoverflow.net/questions/56492/shifts-of-multiplicative-subgroup-of-a-field/56502#56502 Answer by Boris Bukh for Shifts of multiplicative subgroup of a field Boris Bukh 2011-02-24T08:10:27Z 2011-02-24T14:01:12Z <p>In fields of prime order, factoring the difference of squares shows that the number of solutions to $x^2=y^2+c$ is what you expect it to be, from which it follows the intersection $H\cap (H+c)$ has size about what you expect. For triple intersections such as $H\cap (H+1)\cap (H+2)$, one there is an elementary argument for certain values of $p$, but not others (in this example, for $p=3,7\pmod 8$). In general you will need estimate the character sum $$\sum_x \chi(x(x+c_1)(x+c_2)\dotsb(x+c_m))$$ where $\chi$ is the Legendre symbol modulo $p$. This can be estimated by invoking Riemann hypothesis for curves.</p> <p>By the way, if $H$ were a small subgroup of $F*$ (of size $n^{1-\epsilon}$), then the sum-product estimates show that the intersection $|H\cap (H+c)|$ can never be large. See for example, <a href="http://arxiv.org/abs/0811.4206" rel="nofollow">this paper</a> for a related problem of estimating the product of $H$ and $H+c$. </p> <p><strong>The following is wrong since (H+c) is not closed under multiplication:</strong></p> <p>One can get the result for the intersection by using Ruzsa's triangle inequality. Namely, $$|H(H+c)|\leq \frac{|H(H\cap (H+c))||(H+c)(H\cap (H+c))|}{|(H\cap (H+c))|}\leq \frac{|H|^2}{|(H\cap (H+c))|}$$.</p> http://mathoverflow.net/questions/53872/angle-of-a-regular-simplex Angle of a regular simplex Boris Bukh 2011-01-31T09:36:34Z 2011-01-31T12:51:32Z <p>I find the following question embarrassing, but I have not been able to either resolve it, or to find a reference.</p> <blockquote> <p>What is the vertex angle of a regular $n$-simplex?</p> </blockquote> <p>Background: For a vertex $v$ in a convex polyhedron $P$, the vertex angle at $v$ is the proportion of the volume that $P$ occupies in a small ball around $v$. In symbols, $$\angle v=\lim_{\varepsilon\to 0} \frac{|B(v,\varepsilon)\cap P|}{|B(v,\varepsilon)|}.$$ Up to normalization, this definition agrees with the familiar definition of the angles in the plane, or the solid angle in $3$-space.</p> http://mathoverflow.net/questions/44537/is-there-a-free-action-on-a-given-variety Is there a free action on a given variety? Boris Bukh 2010-11-02T10:16:26Z 2010-11-30T13:22:14Z <p>Given a variety $V$, and a prime $p$ I want to decide if there is a free action of $\mathbb{Z}/p\mathbb{Z}$ on $V$, and to find the generator of an action if it exists. Is there a known algorithm to do it? (Assume $V$ is affine over $\mathbb{C}$, and we have a basis for the ideal of $V$.)</p> http://mathoverflow.net/questions/47407/does-sl-3r-embed-in-sl-2r/47420#47420 Answer by Boris Bukh for Does $SL_3(R)$ embed in $SL_2(R)$? Boris Bukh 2010-11-26T11:17:50Z 2010-11-26T11:17:50Z <p>Define a sequence of groups $G_i$ and associated group rings $R_i=\mathbb{Q}[G_i]$. To start put $G_0=\mathbb{Q}$. Then define $G_{i+1}=SL_3(R_i)$. The group $SL_3(R_i)$ is a subgroup of $SL_2(R_{i+1})$ because $G_{i+1}$ is a subgroup of $SL_2(R_{i+1})$ (as the group of certain diagonal matrices). Similarly, $G_i$ is a subgroup of $G_{i+1}$, and hence $R_i$ is a subring of $R_{i+1}$. Then $R=\bigcup_i R_i$ is the ring you want.</p> http://mathoverflow.net/questions/47214/how-to-present-mathematics-to-non-mathematicians/47220#47220 Answer by Boris Bukh for How To Present Mathematics To Non-Mathematicians? Boris Bukh 2010-11-24T11:31:09Z 2010-11-24T11:31:09Z <p>Mathematics is about the reasoning that can be made precise. The different branches of mathematics reason about different objects: numbers, shapes (rigid or stretchy), games, arrangements and relations, and other things for which the words do not exist in the everyday language. There are some branches of mathematics exploring the reasoning itself. Pretty much any set of rules of reasoning one can normally think of is equally powerful (we say <em>equiconsistent</em>). The large cardinals is a name of for various rules that are stronger.</p> <p>To explore reasoning about different things, give a puzzle to the class. Many people like them, and do not think of these as maths. I would consider "hats" puzzles, or some topological puzzle (e.g. is this picture an unknot? are there two antipodal points on the surface of the Earth with the same temperature? etc). There are good puzzles books to get ideas from, such as those by Martin Gardner and Raymond Smullyan.</p> http://mathoverflow.net/questions/46998/what-is-the-shortest-route-to-roths-theorem/47066#47066 Answer by Boris Bukh for What is the shortest route to Roth's theorem? Boris Bukh 2010-11-23T08:04:29Z 2010-11-23T08:04:29Z <p>The most direct argument I know is the original argument of Szemerédi. It is background-free: no regularity lemma, no Fourier analysis. It is also very intuitive. There is a sketch by Ernie Croot at <a href="http://people.math.gatech.edu/~ecroot/szemeredi.pdf" rel="nofollow">http://people.math.gatech.edu/~ecroot/szemeredi.pdf</a></p> http://mathoverflow.net/questions/45284/examples-of-sequences-whose-asymptotics-cant-be-described-by-elementary-function/45292#45292 Answer by Boris Bukh for Examples of sequences whose asymptotics can't be described by elementary functions Boris Bukh 2010-11-08T11:26:07Z 2010-11-08T11:33:00Z <p><a href="http://en.wikipedia.org/wiki/Davenport%E2%80%93Schinzel_sequence" rel="nofollow">Davenport–Schinzel sequences</a> are related to complexity of arrangements of various geometric shapes (e.g. envelopes of line segments). Their asymptotics is described in terms of the inverse Ackermann function.</p> http://mathoverflow.net/questions/44326/most-memorable-titles/44342#44342 Answer by Boris Bukh for Most memorable titles Boris Bukh 2010-10-31T16:11:56Z 2010-10-31T16:11:56Z <p><a href="http://www.jstor.org/stable/2320708" rel="nofollow">An application of Poincaré's recurrence theorem to academic administration</a> by Kenneth Meyer is a title that is hard to resist looking into.</p> http://mathoverflow.net/questions/44096/detecting-whether-directed-cycle-is-clockwise-or-counterclockwise/44098#44098 Answer by Boris Bukh for Detecting whether directed cycle is clockwise or counterclockwise Boris Bukh 2010-10-29T10:03:00Z 2010-10-29T10:03:00Z <p>The orientation of a triangle (clockwise/counterclockwise) is the sign of the determinant $\begin{bmatrix} 1&amp;x_1&amp;y_1\\ 1&amp;x_2&amp;y_2\\ 1&amp;x_3&amp;y_3 \end{bmatrix}$, where $(x_1,y_1), (x_2,y_2), (x_3,y_3)$ are the Cartesian coordinates of the three vertices of the triangle.</p> http://mathoverflow.net/questions/43995/are-any-good-strategies-known-for-erdos-turan-conjecture-on-additive-bases-of-ord/44004#44004 Answer by Boris Bukh for Are any good strategies known for Erdos-Turan conjecture on additive bases of order two? Boris Bukh 2010-10-28T19:20:43Z 2010-10-28T19:20:43Z <p>It is fair to say that no one has a clue. There are two current ideas for "attack":</p> <p>1) Erdős-Fuchs theorem which asserts that it is not the case that $r$ is nearly constant</p> <p>2) The argument of Erdős that if $r(n)\leq 1$ for all $n$ (such a $B$ is called Sidon set), then $\liminf |B\cap \{1,\dotsc,n\}|/\sqrt{n/\log n}&lt;100$</p> <p>The proofs of both results can be found in the <a href="http://www.ams.org/mathscinet-getitem?mr=687978" rel="nofollow">lovely book by Halberstam and Roth</a>. Sandor's result is similar to Erdős-Fuchs, but puts a clever twist on it, which permits him to prove a result as strong as his. The argument of Erdős <a href="http://www.ams.org/mathscinet-getitem?mr=1234964" rel="nofollow">has been successfully extended</a> to Sidon set of even order (that means that all sums of $2m$ terms are distinct). It might sound trivial since if $B$ is a Sidon set of order $2m$, then $m$-fold sumset of $B$ with itself is almost a Sidon set, but does need to do work to get around this almost''. It is an open problem whether there is an extension to Sidon sets of odd order.</p> http://mathoverflow.net/questions/42512/awfully-sophisticated-proof-for-simple-facts/42513#42513 Answer by Boris Bukh for Awfully sophisticated proof for simple facts Boris Bukh 2010-10-17T15:41:06Z 2010-10-17T15:41:06Z <p>There are infinitely many primes because $\zeta(3)=\prod_p \frac{1}{1-p^{-3}}$ is irrational.</p> http://mathoverflow.net/questions/130408/using-simplex-to-solve-systems-of-linear-inequalities Comment by Boris Bukh Boris Bukh 2013-05-12T12:59:15Z 2013-05-12T12:59:15Z This question is off-topic for the website (it is not research-level). See FAQ for a list of better places to ask. http://mathoverflow.net/questions/130264/dominating-set-in-a-r-uniform-hypergraph Comment by Boris Bukh Boris Bukh 2013-05-10T14:16:35Z 2013-05-10T14:16:35Z First, this question is off-topic for this website (it is not research-level). See FAQ. Second, you can find a solution (for r=2) in the book &quot;Probabilistic method&quot; by Alon and Spencer, which I would recommend as the best introduction to the subject. http://mathoverflow.net/questions/129204/intersection-of-2-visibility-polygons/129208#129208 Comment by Boris Bukh Boris Bukh 2013-04-30T14:51:00Z 2013-04-30T14:51:00Z Well, Joseph O'Rourke wrote a book on art gallery theorems. :-) http://mathoverflow.net/questions/128981/bounding-a-recursively-defined-sequence Comment by Boris Bukh Boris Bukh 2013-04-29T14:58:15Z 2013-04-29T14:58:15Z How about using the estimate for $\lambda_k$ that you obtained, when estimating the second $\max$? Currently, for estimates that $\max$ you bound $\lambda_k$ by $1$. It is the bootstrapping method popularized by M&#252;nchausen :-) http://mathoverflow.net/questions/126039/reverse-gausss-circle-problem Comment by Boris Bukh Boris Bukh 2013-03-31T02:27:10Z 2013-03-31T02:27:10Z What is the exact statement of the problem you want to solve. How is it different than Gauss' problem? http://mathoverflow.net/questions/125914/finite-vertex-transitive-graphs-that-look-like-infinite-vertex-transitive-graphs/125937#125937 Comment by Boris Bukh Boris Bukh 2013-03-29T21:28:57Z 2013-03-29T21:28:57Z I am sorry, but I remain unconvinced. We see the loops, but how do we write from knowing the loops the relations? The edges are not labelled with the names of generators. So, we do not know that two &quot;parallel-looking&quot; edges correspond to the same generator. http://mathoverflow.net/questions/125914/finite-vertex-transitive-graphs-that-look-like-infinite-vertex-transitive-graphs/125937#125937 Comment by Boris Bukh Boris Bukh 2013-03-29T20:49:04Z 2013-03-29T20:49:04Z For the original question, isn't it conceivable that an infinite graph has symmetry group $G$, but for every $d$ there is a group $G_d$ and a set of generators such that the Cayley graph looks like $G$ in a neighborhood of size $d$, but these groups $G_d$ have nothing whatsoever to do with the original $G$? http://mathoverflow.net/questions/125739/choosing-subsets-with-half-the-elements-in-common Comment by Boris Bukh Boris Bukh 2013-03-27T17:41:15Z 2013-03-27T17:41:15Z Look up Frankl--Wilson, and Ray--Chaudhury--Wilson theorems. http://mathoverflow.net/questions/125479/understanding-fourier-coefficients Comment by Boris Bukh Boris Bukh 2013-03-24T19:44:29Z 2013-03-24T19:44:29Z This question would be more appropriate at math.stackexchange.com See FAQ. http://mathoverflow.net/questions/125214/combining-van-der-waerdens-theorem-with-ramseys-theorem Comment by Boris Bukh Boris Bukh 2013-03-22T00:49:39Z 2013-03-22T00:49:39Z It is already known to be false. Each 2-tuple is in an essentially unique s-AP. http://mathoverflow.net/questions/124888/a-generalisation-of-sperner-families-union-free-families Comment by Boris Bukh Boris Bukh 2013-03-19T15:07:19Z 2013-03-19T15:07:19Z Theorem 8.13 from the book that you linked to seems to answer the question. In your case $n=ck$ and $r=k$, which gives $t=1$ and so $|\mathcal{F}|\leq k+n$. Hence there are no &quot;non-trivial&quot; families. http://mathoverflow.net/questions/124888/a-generalisation-of-sperner-families-union-free-families Comment by Boris Bukh Boris Bukh 2013-03-19T13:34:13Z 2013-03-19T13:34:13Z Union-free family is a different beast entirely! A family is a k-union-free if union of k set is not <i>equal</i> to a set in a family. You ask about containment, not equality. What are you really interested in? http://mathoverflow.net/questions/123776/best-mathematic-field-for-phd Comment by Boris Bukh Boris Bukh 2013-03-06T15:55:28Z 2013-03-06T15:55:28Z Math PhD is not for you if you do it for career uplifting. It will be a waste of five years of your life. http://mathoverflow.net/questions/123111/number-of-graphs-with-a-cycle Comment by Boris Bukh Boris Bukh 2013-02-27T16:37:42Z 2013-02-27T16:37:42Z No answer in the literature? Where did you search? It is a classic problem. http://mathoverflow.net/questions/123111/number-of-graphs-with-a-cycle Comment by Boris Bukh Boris Bukh 2013-02-27T15:37:40Z 2013-02-27T15:37:40Z Please provide the motivation, and explain what you tried. See <a href="http://mathoverflow.net/howtoask" rel="nofollow">mathoverflow.net/howtoask</a>