User yuval filmus - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T09:45:36Z http://mathoverflow.net/feeds/user/7732 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/94438/beyond-hilton-milner-theorem-for-an-intersecting-family/127781#127781 Answer by Yuval Filmus for Beyond Hilton-Milner Theorem for an Intersecting Family? Yuval Filmus 2013-04-17T02:44:39Z 2013-04-17T02:44:39Z <p>There are at least three types of results that spring to mind. One is the Ahlswede-Khachatrian theorem ("the complete intersection theorem"), which for each $n$ and $k &lt; n/2$ will give you tight upper bounds for $t$-intersecting families (families in which every two sets intersect in at least $t$ points). For example, if $k \leq n/3 + 1$ then a $2$-intersecting family has size at most $\binom{n-2}{k-2}$, and so if $|\mathcal{F}| > \binom{n-2}{k-2}$ then there are two sets $S,T \in \mathcal{F}$ such that $|S \cap T| = 1$. They also have a matching Hilton-Milner type result, in which the family is required to have empty intersection ("the complete non-trivial intersection theorem").</p> <p>A second one is stability results. Such results show that if $|\mathcal{F}| = (1-\epsilon)\binom{n-1}{k-1}$ then there is an element belonging to a $1-O(\epsilon)$ fraction of the sets. One such result is due to Friedgut ("on the measure of intersecting families, uniqueness and stability", another is due to Keevash ("shadows and intersections: stability and new proofs").</p> <p>A third one is due to Dinur and Friedgut ("intersecting families are essentially contained in juntas"). For $k = cn$, they show that <em>any</em> intersecting family essentially depends on $O(1)$ points, where the constant depends on $c$. For $k = o(n)$, they can show that <em>any</em> intersecting family has an element common to all but $C \binom{n-2}{k-2}$ of the sets.</p> http://mathoverflow.net/questions/88260/pade-approximations-of-e Padé approximations of $e$ Yuval Filmus 2012-02-12T05:27:28Z 2012-02-12T18:25:22Z <p>The following question came up in the analysis of some algorithm.</p> <p>Let $R_{s,t}(z)$ be the Padé approximants of $e^z$, and define $r_{s,t} = R_{s,t}(1)$. Using the explicit expression for the error term of the Padé approximant, it is easy to see that $$(-1)^t e > r_{s,t}.$$ We focus on a secondary diagonal $s + t = n$ for $n \geq 2$. Its entries $r_{n,0},r_{n-1,1},\ldots,r_{0,n}$ are alternately lower bounds and upper bounds on $e$. The sequence of lower bounds has the property that $$r_{n,0} &lt; r_{n,2} &lt; \cdots &lt; r_{n-2\lfloor n/4\rfloor,2\lfloor n/4\rfloor} \geq r_{n-2\lfloor n/4\rfloor-2,2\lfloor n/4\rfloor+2} > \cdots,$$ with equality when $n = 4k+3$. The sequence of upper bounds enjoys a similar property: $$r_{n,1} > r_{n,3} > \cdots > r_{n-2\lfloor (n-2)/4 \rfloor - 1,2\lfloor (n-2)/4 \rfloor + 1} \leq r_{n - 2\lfloor (n-2)/4 \rfloor - 3,2\lfloor (n-2)/4 \rfloor + 3} &lt; \cdots,$$ with equality when $n = 4k+1$. So the tightest lower and upper bounds appear in the middle of any secondary diagonal.</p> <p>These properties of the sequence $r_{n,0},\ldots,r_{0,n}$ were observed experimentally. Why do they hold?</p> <p>Edit: Let $I_n = [r_{n-2\lfloor n/4\rfloor,2\lfloor n/4\rfloor}, r_{n-2\lfloor (n-2)/4 \rfloor - 1,2\lfloor (n-2)/4 \rfloor + 1}]$ be the interval constituting of the best bounds in the secondary diagonal $s+t=n$. Then experimentally, $$I_2 \supset I_3 \supset I_4 \supset \cdots,$$ i.e. the bounds get tighter. Why is that?</p> <p>(Using the explicit expression for the error term, it is easy to prove that $\bigcap_{n=2}^\infty I_n = \{e\}$.)</p> http://mathoverflow.net/questions/57906/frobenius-norms-of-fourier-coefficients-of-the-symmetric-group Frobenius norms of Fourier coefficients of the symmetric group Yuval Filmus 2011-03-09T03:24:15Z 2011-03-09T03:24:15Z <p>Suppose $f \colon S_n \rightarrow \mathbb{R}$ is some weighted collection of permutations. We want to understand how "well-spread" $f$ is. Our first test is its actions on singletons - are the statistics of how many permutations send $i$ to $j$ "random"?</p> <p>To make this question more precise, define $|f| = \sum_\pi f(\pi)$ to be the total number of permutations in $f$ (i.e. their total weight), $A_{ij}$ to be the number of permutations in $f$ sending $i$ to $j$, and $B_{ij} = A_{ij} - |f|/n$. The matrix $B$ is just a normalized form of $A$ - its row and column sums are zero. A measure of spread is the Frobenius norm of $B$, i.e. $\sum_{i,j} B_{ij}^2$.</p> <p>Consider now the Fourier transform of $f$. For each partition $\rho$, there is some Fourier coefficient $\hat{f}(\rho)$ which is some (square) matrix. We know that the coefficient of $(n)$ characterizes $|f|$, and the coefficients of $(n)$ and $(n-1,1)$ together characterize the action on singletons. Since we have erased the effects of $\hat{f}((n))$ by moving from $A$ to $B$, it should not come as a surprise that the Frobenius norms of $B$ and of $\hat{f}((n-1,1))$ are linearly related - that's what I seem to get.</p> <blockquote> <p>Is it correct that the Frobenius norm of $B(f)$ is equal to some constant multiple (depending on $n$) of $\hat{f}((n-1,1))$?</p> <p>Can the result be extended to other Fourier coefficients? What data corresponds to a partition $\rho$? In particular, what partitions capture the effect of $f$ on $k$-tuples? (the answer should be something like all partitions whose first part is $n-k$)</p> </blockquote> http://mathoverflow.net/questions/45510/big-o-notation-and-the-maximal-set-of-comparable-functions/45517#45517 Answer by Yuval Filmus for Big O notation and the maximal set of comparable functions Yuval Filmus 2010-11-10T04:47:20Z 2010-11-10T04:47:20Z <p>There is no countable chain which is maximal: if $f_i$ is a sequence of functions, then define</p> <p>$g(n) = n \cdot \max_{i \leq n} f_i(i)$</p> <p>The function $g$ grows faster than all the functions in the sequence.</p> <p>So there's probably no simple explicit construction other than the one obtained through transfinite induction.</p> <p>You could ask what is the (minimal/maximal) cardinality of a maximal sequence - that probably depends on cardinal characteristics of the continuum (given the CH it's $\aleph_1$ since you can take all piecewise linear functions whose values at the natural numbers are all natural).</p> <p>You can further ask what happens if the functions need to be recursive - that's the <a href="http://en.wikipedia.org/wiki/Fast-growing_hierarchy" rel="nofollow">fast-growing hierarchy</a>.</p> http://mathoverflow.net/questions/45182/asymptotics-for-forbidden-subwords/45184#45184 Answer by Yuval Filmus for Asymptotics for forbidden subwords Yuval Filmus 2010-11-07T17:54:48Z 2010-11-08T19:58:39Z <p>If you fix $B$ then the situation is described by a DFA (deterministic finite automaton), i.e. the set of permissible words is a regular language, and so has a rational generating function; therefore, the number of permissible words grows either exponentially or polynomially.</p> <p>Re your general question, if you take $B = \{ a : a \in A \}$ (or better, $B$ consists of the empty word) then there are no permissible words. On the other hand, if all the words in $B$ have size greater than $n$, then all words are permissible. So $n = k^{1+\epsilon}$ is not really meaningful.</p> <p>Maybe you're worried that the last example (all words in $B$ are bigger than $n$) is cheating. You can take $A = \{a,b,c,d\}$ and $B = \{a^kb^{m-k} : 0 \leq k \leq m \}$. The set $B$ is reduced (i.e. no word is a subword of any other word), and yet the number of permissible words is exponential; we can construct such sets $B$ with arbitrary size.</p> <p>It seems reasonable (see Bill's comment below) to assume that the set of words under the subword relation is a wqo (well-quasi-ordering), and so there is no infinite reduced $B$. Therefore we can't ask whether there's an infinite reduced $B$ which allows exponential growth; if $B$ need not be reduced, take $B = \{a^m : m \geq 1\}$.</p> <p>Edited to explain the acronyms re Bill's comment.</p> http://mathoverflow.net/questions/45185/pseudonyms-of-famous-mathematicians/45191#45191 Answer by Yuval Filmus for Pseudonyms of famous mathematicians Yuval Filmus 2010-11-07T18:30:23Z 2010-11-07T18:30:23Z <p>Felix Hausdorff published philosophical and literary books as Paul Mongré.</p> <p>Let me mention that Hausdorff committed suicide (along with his wife) in 1942, to prevent his being sent to a concentration camp. He had tried to escape to the US, but unfortunately no one would sponsor him. So he joined the ranks of mathematicians who were victims of World War II (including some Germans who died at Soviet hands, for example Gentzen). </p> http://mathoverflow.net/questions/44506/connective-constant-for-self-avoiding-walks-on-a-skip-chain/44532#44532 Answer by Yuval Filmus for Connective constant for self-avoiding walks on a skip-chain Yuval Filmus 2010-11-02T09:36:21Z 2010-11-02T09:36:21Z <p>A step is a movement of magnitude 1, a hop of magnitude 2.</p> <p>Denote by $X$ a visited place, by $O$ a place not visited, and by $Y$ the current position. A self-avoiding walk hovers around the states $E_n$, in which the relevant part of the integer line is $X(XO)^nXY$. From this state, the walk can proceed as follows:</p> <ol> <li>Hop left $n$ times and get stuck.</li> <li>Step right to reach $E_0$.</li> <li>Hop right, step left, hop right, reaching $E_0$.</li> <li>Hop $m\geq 1$ times right, then step right, reaching $E_m$.</li> <li>Hop $m\geq 2$ times right, step left, hop $m-1$ times left and get stuck.</li> <li>Hop $m\geq 2$ times right, step left, then hop right, reaching $E_0$.</li> </ol> <p>Options 1,5, where the walk gets stuck, seem not to affect the asymptotics (handwaving). Since option 1 is the only one where $n$ (the subscript of $E_n$) matters, we can disregard the subscripts, and just call it $E$.</p> <p>So we get from $E$ to $E$ by one of the following:</p> <ol> <li>Step right.</li> <li>Hop right, step left, hop right.</li> <li>Hop $m \geq 1$ times right, step right.</li> <li>Hop $m \geq 2$ times right, step left, hop right.</li> </ol> <p>In terms of number of steps, these are $1;3;2,3,4,\ldots;4,5,6,\ldots$. In total, we have "bricks" of sizes $1,2$, and two bricks each of sizes $3,4,\ldots$. The corresponding generating series is</p> <p>$1/(1-x-x^2-2x^3/(1-x)) = (1-x)/(1-2x-x^3)$</p> <p>The denominator has one real root, about 0.453397651516404. So the $k$ term is $O(2.20556943040059^k)$.</p> <p>A walk of length $\ell$ reaches state $E$ after one of $O(\ell^2)$ prefixes, some of which are short. So up to a polynomial, the number of walks is the same as the number of walks starting with $E$. Thus $\mu = 2.20556943040059$.</p> http://mathoverflow.net/questions/43924/when-are-infinitely-many-points-in-the-orbit-of-a-polynomial-integers When are infinitely many points in the orbit of a polynomial integers? Yuval Filmus 2010-10-28T01:45:34Z 2010-10-28T16:50:14Z <p>This question is inspired by a <a href="http://math.stackexchange.com/questions/8101/iterated-polynomial-problem" rel="nofollow">riddle</a> in math.stackexchange.</p> <p>Let $P$ be a polynomial, and $O = \{P^{(n)}(0) : n \geq 0\}$ be its orbit under zero (viewed as a set). Suppose that $O$ contains infinitely many integers. Is it true that for some $n$, $P^{(n)}$ is a polynomial with integral coefficients?</p> <p>We can ask the same question replacing integers with rationals.</p> <p>EDIT: Nick and David gave simple counterexamples for the first question. Still open:</p> <ol> <li>In the setting of the original question, is it true that some composition power of $P$ takes integers to integers?</li> <li>The original question with rationals.</li> </ol> http://mathoverflow.net/questions/38460/arithmetic-of-ordered-sets-more-general-than-ordinals/38519#38519 Answer by Yuval Filmus for Arithmetic of ordered sets more general than ordinals Yuval Filmus 2010-09-12T23:43:54Z 2010-09-12T23:43:54Z <p>I recommend Rosenstein's excellent book "Linear orderings".</p> http://mathoverflow.net/questions/36714/notation-for-a-graph-without-any-edges Notation for a graph without any edges? Yuval Filmus 2010-08-26T03:48:44Z 2010-08-26T11:32:55Z <p>Is there a standard notation for a graph (on a given set of vertices) without any edges?</p> http://mathoverflow.net/questions/35834/how-many-pairs-of-edges-can-disconnect-a-biconnected-graph How many pairs of edges can disconnect a biconnected graph? Yuval Filmus 2010-08-17T04:26:28Z 2010-08-17T12:54:47Z <p>Consider some biconnected graph $G$. Removing any single edge will not disconnect $G$. However, unless $G$ is triconnected, there is some pair of edges whose removal will disconnect $G$. For a cycle of length $l$, the removal of any pair will disconnect the graph (if the edges are adjacent, there will be an isolated vertex).</p> <blockquote> <p>Conjecture: any biconnected graph on $l$ vertices has at most $\binom{l}{2}$ pairs of edges that disconnect it. Furthermore, the bound is tight only for cycles.</p> </blockquote> <p>Is the conjecture true? I have a candidate proof but I suspect that there's a simpler one.</p> http://mathoverflow.net/questions/32552/characterization-of-trees-in-terms-of-products-of-transpositions/32578#32578 Answer by Yuval Filmus for characterization of trees in terms of products of transpositions Yuval Filmus 2010-07-20T02:35:29Z 2010-08-13T15:08:56Z <p>Notation: &alpha;&beta; means apply &alpha; then &beta;.</p> <p>If the graph is not a tree, then either it contains a cycle or it contains less than n&minus;1 edges. In the latter case, we get a contradiction since less than n&minus;1 transpositions cannot multiply to a big cycle.</p> <p>So suppose that the graph contains a cycle (12...k), and assume that for each order of the edges, you get a big cycle. In particular, this holds for orderings where you take the cycle last. Fix some ordering of the other edges, and denote the interim product (without the edges of the cycle) by &pi;. So for each product &sigma; of the edges of the cycle, &pi;&sigma; is a long cycle.</p> <p>For each i&lt;j, there is some ordering of the cycle which produces a permutation containing the transposition (ij). Indeed, take (i i+1)(i+1 i+2)...(j-2 j-1) (j j+1) ... (k 1) (1 2) ... (i-1 i) (j-1 j).</p> <p>Thus for each i&lt;j, &pi;(ij)&tau; is a big cycle, where &tau; does not involve i or j. In particular, &pi;(i)&ne;j. Since this is true for all i&ne;j, it follows that &pi; must be the identity. We get a contradiction since &sigma; is not a big cycle.</p> http://mathoverflow.net/questions/34070/motivation-of-moment-generating-functions/34071#34071 Answer by Yuval Filmus for Motivation of Moment Generating Functions Yuval Filmus 2010-08-01T00:15:25Z 2010-08-01T00:15:25Z <p>If X and Y are independent then $E[e^{t(X+Y)}] = E[e^{tX}] E[e^{tY}]$, so convolution corresponds to multiplication of the mgf's. Another reason: the moment generating function is actually a Fourier transform.</p> <p>Now suppose $X_i$ are i.i.d. with zero mean, and define $Y_n = \sum_{i=1}^n X_i/\sqrt{n}$. Define $\phi(t) = E[e^{tX_1}]$. Then $E[e^{tY_n}] = \phi(t/\sqrt{n})^n$. Under reasonable assumptions, $\phi(t) = 1 + V[X_1]t^2/2 + O(t^3)$, and so $E[e^{tY_n}] = (1 + V[X_1]t^2/2n + O(t^3)/n^{1.5})^n \longrightarrow e^{V[X_1]t^2/2}$, and we get the central limit theorem (by continuity of the Fourier transform). </p> http://mathoverflow.net/questions/31448/lower-bounds-in-theoretical-computer-science/33172#33172 Answer by Yuval Filmus for Lower Bounds in Theoretical Computer Science Yuval Filmus 2010-07-24T06:14:09Z 2010-07-24T06:14:09Z <p>Union-find data structures have an inverse-Ackermann lower bound &Omega;(<i>n &alpha;</i>(<i>n</i>)), see Wikipedia.</p> http://mathoverflow.net/questions/32891/finding-the-largest-integer-describable-with-a-string-of-symbols-of-predefined-le/32895#32895 Answer by Yuval Filmus for Finding the largest integer describable with a string of symbols of predefined length Yuval Filmus 2010-07-22T04:15:52Z 2010-07-22T04:15:52Z <p>Given a computable function f(n), the function g(n) = nf(n) is also computable and dominates it.</p> <p>Similarly, given a non-computable function f(n), the function g(n) = f(n)/n is also non-computable (let's ignore the fact that f(n) need not be divisible by n) and is dominated by it.</p> <p>So F can be neither computable nor non-computable. In classic logic we've reached a contradiction.</p> <p>Another problem with your definition is that you might have incomparable functions, i.e. functions where the test is inconclusive.</p> http://mathoverflow.net/questions/32437/when-do-cofinal-chains-of-universal-codings-of-the-integers-exist When do cofinal chains of universal codings of the integers exist? Yuval Filmus 2010-07-19T02:23:32Z 2010-07-21T22:24:38Z <h3>Universal codings of integers</h3> <p>A (binary) <em>coding of the integers</em> is a prefix-free code of the natural numbers, whose codewords are non-decreasing in size. A coding is <em>universal</em> if it is short enough (log n + o(log n)), but that's not important.</p> <p>Some examples:</p> <ul> <li>The unary coding 0, 10, 110, ...; code length is n</li> <li>Code first the length of the number in unary, then the number itself in binary; code length is about 2log n</li> <li>Code first the length of the number using the previous coding, then the number itself in binary; code length is about log n + 2log log n</li> <li>...</li> <li>Diagonalize the construction to get code length of log n + log log n + ... + 2log<sup>*</sup> n</li> <li>Continue this way through the constructible ordinals</li> </ul> <p>The diagonalized code, known as the $\omega$-code, is due to Peter Elias.</p> <h3>A partial ordering of codes</h3> <p>The sequence of codes above are progressively better, in the following sense:</p> <ul> <li>A coding a is better than a coding b if |b(n)| - |a(n)| tends to infinity.</li> </ul> <p>There are some natural questions to ask:</p> <ul> <li>Is there a best code?</li> <li>If not, is there an optimal sequence of codes?</li> </ul> <p>As it turns out, not only is there no <em>best</em> code, but given any sequence of codes, we can always find a code which is better than <em>all</em> of them; the proof from one of Hausdorff's papers (Untersuchungen &uuml;ber Ordnungtypen V from 1907) can be adapted to our setting.</p> <h3>Scales</h3> <p>The best thing that can be hoped for is a <em>chain</em> of codes which is cofinal for the poset of codes, i.e. a set of mutually comparable codings, such that for each arbitrary coding, our scale contains a superior one (such a beast Hausdorff called a Pantachie).</p> <p>The problem of scales is well-known, and it is easy to show the existence of a scale given CH (following Hausdorff's steps). In other settings (and possibly this one), existence already follows from MA. However, most of the literature deals with somewhat different posets, and it is not clear that their results apply in this case.</p> <p>Here are some pointers:</p> <ul> <li><em>Hausdorff Gaps and Limits</em> by Frankiewicz and Zbierski, which deals with the ordering f > g if f(n) > g(n) infinitely often.</li> <li><em>Gaps in $\omega^\omega$</em> by Marion Scheepers, which deals with the ordering f > g if f(n) - g(n) tends to infinity.</li> </ul> <p>In their settings, Hechler forcing can be used to produce worlds in which there is no scale.</p> <blockquote> <p>Is the existence of scale (in the context of monotone codings of integers) independent of set theory?</p> </blockquote> <h3>Codings and series</h3> <p>Some easy reductions connect our problem with problems involving convergent series and divergent series satisfying some extra conditions, which stem from our monotonicity requirements; the key is Kraft's inequality, stating that a code with codeword lengths w<sub>i</sub> exists iff the sum $\sum 2^{-w_i}$ converges.</p> <p>The reductions are most easily stated if we extend our posets with some equivalence relation. We then say that two posets are <em>interlacing</em> if there are two order-preserving mappings (between the two posets in both directions) which are pseudo-inverses, i.e. their composition sends a point to an equivalent one. Given two interlacing posets, one has a scale iff the other one has a scale.</p> <p>The following posets are interlacing:</p> <ul> <li>Arbitrary (non-monotone) codes, with a &lt; b if b is better than a, and a ~ b if |a(n)-b(n)| is bounded.</li> <li>Convergent positive series, with a &lt; b if b(n) = o(a(n)), and a ~ b if a(n) = O(b(n)) and b(n) = O(a(n)).</li> <li>Divergent positive series (reverse definition of &lt;).</li> </ul> <p>Monotonicity complicates the picture (the corresponding series are no longer arbitrary) but seems necessary, since one can give a non-monotone code with the property that no monotone code is better than it.</p> <h3>Effective and efficient codings</h3> <p>The motivation behind the question is the actual usage of universal codings by computer engineers. New, impractical methods of codings are suggested all the time, but no one seems to have tackled the fundamental question.</p> <p>This prompts us to ask similar questions for effective (computable) codings.</p> <blockquote> <p>Can classical recursion theory hierarchies be adapted to the setting of codes?</p> </blockquote> <p>It would be nice to get an analog of the fast-growing hierarchy, for example.</p> <p>We could further wonder what happens if we ask our coding procedure to be efficient, for example linear-time computable.</p> http://mathoverflow.net/questions/32730/does-an-efficient-random-number-generator-exist/32741#32741 Answer by Yuval Filmus for Does an "efficient" random number generator exist? Yuval Filmus 2010-07-21T03:49:47Z 2010-07-21T03:49:47Z <p>I assume that n is a power of 2.</p> <p>You can try an LFSR (check Wikipedia), but that will cycle (given the correct feedback) only over the non-zero integers in your range.</p> <p>Another possibility is the map x += (x*x) | 5, where you can actually replace 5 with any number of the form 8n+5. I don't remember the reference for that.</p> http://mathoverflow.net/questions/32588/n-widths-and-kolmogorovs-entropy/32591#32591 Answer by Yuval Filmus for n-widths and Kolmogorov's entropy Yuval Filmus 2010-07-20T04:22:33Z 2010-07-20T04:22:33Z <p>You can try <i>An Introduction to Kolmogorov Complexity and Its Applications</i> by Ming Li and Paul Vit&aacute;nyi, it's an excellent book.</p> http://mathoverflow.net/questions/32553/enumerative-combinatorics-with-fixed-number-repeats/32573#32573 Answer by Yuval Filmus for enumerative combinatorics with fixed number repeats Yuval Filmus 2010-07-20T01:28:52Z 2010-07-20T01:28:52Z <p>Suppose we have <i>n</i> elements, we want to generate <i>r</i> elements (without order), and want exactly <i>k</i> elements to be repeated.</p> <p>We can separate the result into a part containing all the repeated elements (the <i>repeating</i> part) and all the rest (the <i>non-repeating</i> part). Suppose the repeating part is of length <i>m</i>. There are $\binom{n}{k}$ ways to choose the distinct elements in the repeating part. Each of them appears at least twice, and the other <i>m</i>&minus;2<i>k</i> elements are arbitrary, so can be chosen in $\binom{m-k-1}{k-1}$ ways. There are $\binom{n-k}{r-m}$ possible choices for the non-repeating part.</p> <p>Putting it all together:</p> <blockquote> <p>$\binom{n}{k} \sum_{m=2k}^r \binom{m-k-1}{k-1} \binom{n-k}{r-m}$</p> </blockquote> <p>If you want to allow less repeating elements, just sum over <i>k</i> as well.</p> http://mathoverflow.net/questions/32434/what-is-the-limiting-distribution-of-local-minima-of-n-mod-i-for-i-up-to-sqrt What is the limiting distribution of local minima of n mod i, for i up to $\sqrt{n}$, as $n \rightarrow \infty$? Yuval Filmus 2010-07-19T01:32:13Z 2010-07-19T01:32:13Z <h3>The sequence n mod i</h3> <p>Consider the sequence n mod i for i=1...$\sqrt{n}$. If we draw the sequence as an xy-plot, we get a dense triangle (since n mod i &lt; i). More precisely, the limiting density of the figure is uniform across the allowable triangle (I think you can prove this using Weyl's equidistribution criterion).</p> <h3>Local minima of the sequence</h3> <p>Now suppose we take only local minima of the sequence. If we do this, we get <a href="http://www.cs.toronto.edu/~yuvalf/Elfi.pdf" rel="nofollow">what look like dense triangles</a> (beware: slowly loading!), with some <em>outliers</em> between the triangles. One explanation goes like this: $n \mod i = i \cdot frac(n/i)$; if <em>i</em> is increased or decreased by 1, the change will be roughly $i \cdot frac(n/i^2)$; so a local minimum must always lie below $i \cdot sfrac(n/i^2)$ (sfrac is the distance to the closest integer). This accounts for the 'triangles' (enumerate over the integer closest to $n/i^2$ and its direction). Outliers are explained by our approximation being especially bad when $sfrac(n/i^2)$ is small.</p> <blockquote> <p>What is the limiting density (if any) of this sequence? How many outliers are there, asymptotically?</p> </blockquote> <p>In order to make the question of density meaningful, we need to normalize the axes through division by $\sqrt{n}$. The weight of each point should be $1/\sqrt{n}$.</p> <h3>Further iterations</h3> <p>The process of taking local minima can be iterated. Local maxima can also be mixed. Using reasoning similar to the above, one can come up with equations for the limiting curves, which conform with experimental data. The equations can be found in the pdf linked to above. </p> http://mathoverflow.net/questions/7493/a-riddle-about-zeros-ones-and-minus-ones/32425#32425 Answer by Yuval Filmus for A riddle about zeros, ones and minus-ones Yuval Filmus 2010-07-18T23:23:34Z 2010-07-18T23:23:34Z <p>Another answer (I guess they must be equivalent):</p> <ul> <li>Write each <em>original</em> line as a difference of two 0/1 vectors.</li> <li>Adapt this representation to the modified lines by changing <em>only the subtrahends</em>.</li> <li>You now have a function from {0,1}^n to {0,1}^n. Find a cycle.</li> </ul> http://mathoverflow.net/questions/88260/pade-approximations-of-e Comment by Yuval Filmus Yuval Filmus 2012-02-12T18:16:35Z 2012-02-12T18:16:35Z The continued fraction expansion apparently involves only diagonal or near-diagonal elements. But formulas for the Pad&#233; approximants do appear in Perron's text on continued fractions. http://mathoverflow.net/questions/54915/weakly-regular-graphs Comment by Yuval Filmus Yuval Filmus 2011-08-15T20:22:16Z 2011-08-15T20:22:16Z Crossposted on math.stackexchange: <a href="http://math.stackexchange.com/questions/21230/weakly-regular-graphs" rel="nofollow" title="weakly regular graphs">math.stackexchange.com/questions/21230/&hellip;</a> http://mathoverflow.net/questions/54051/random-permutations-of-z-n/54055#54055 Comment by Yuval Filmus Yuval Filmus 2011-02-02T03:50:14Z 2011-02-02T03:50:14Z Your lower bound is $\Omega(\sqrt{n}/2^n)$ whereas your upper bound is $O((e/2)^n/\sqrt{n})$. So you can't expect to get an upper bound of $O(2^{-n})$, and your upper bound is not very helpful (larger than $1$). http://mathoverflow.net/questions/53884/can-a-polynomial-size-cfg-describe-the-finite-language-w-piw-piw-is Comment by Yuval Filmus Yuval Filmus 2011-01-31T18:36:35Z 2011-01-31T18:36:35Z cross-posted in math.stackexchange: <a href="http://math.stackexchange.com/questions/19691/can-a-polynomial-size-cfg-describe-the-finite-language-w-piw-piw-is" rel="nofollow" title="can a polynomial size cfg describe the finite language w piw piw is">math.stackexchange.com/questions/19691/&hellip;</a> http://mathoverflow.net/questions/51765/a-special-class-of-regular-languages-circular-languages-is-it-known Comment by Yuval Filmus Yuval Filmus 2011-01-13T15:05:44Z 2011-01-13T15:05:44Z @vincenzoml: See my answer on cstheory, part 3. As you mention, the correct normal form is a union of $r^+$'s, which unfortunately in general cannot be disjoint. http://mathoverflow.net/questions/51765/a-special-class-of-regular-languages-circular-languages-is-it-known/51828#51828 Comment by Yuval Filmus Yuval Filmus 2011-01-12T16:37:03Z 2011-01-12T16:37:03Z In fact, a language is circular iff it's the &lt;i&gt;union&lt;/i&gt; of expressions of the form $r^*$. http://mathoverflow.net/questions/51765/a-special-class-of-regular-languages-circular-languages-is-it-known Comment by Yuval Filmus Yuval Filmus 2011-01-12T16:35:53Z 2011-01-12T16:35:53Z Cross-posted on cstheory: <a href="http://cstheory.stackexchange.com/questions/4254/a-special-class-of-regular-languages-circular-languages-is-it-known" rel="nofollow" title="a special class of regular languages circular languages is it known">cstheory.stackexchange.com/questions/4254/&hellip;</a>. http://mathoverflow.net/questions/51506/graph-properties-definability-and-decidability/51514#51514 Comment by Yuval Filmus Yuval Filmus 2011-01-09T04:44:32Z 2011-01-09T04:44:32Z Some take it as part of the definition of &quot;graph property&quot;. http://mathoverflow.net/questions/45995/how-can-express-l3-in-the-given-values Comment by Yuval Filmus Yuval Filmus 2010-11-14T00:30:22Z 2010-11-14T00:30:22Z Please repost in math.stackexchange.com . http://mathoverflow.net/questions/45510/big-o-notation-and-the-maximal-set-of-comparable-functions/45516#45516 Comment by Yuval Filmus Yuval Filmus 2010-11-10T04:49:37Z 2010-11-10T04:49:37Z Can't you add $f(x)=x$ to your set? http://mathoverflow.net/questions/39538/what-is-the-naming-reason-of-poles-in-complex-analysis/45137#45137 Comment by Yuval Filmus Yuval Filmus 2010-11-07T06:47:38Z 2010-11-07T06:47:38Z &quot;When a function u is holomorphic in a certain part of the plane, except for one point z_1, where it becomes infinite, similar to the function 1/u which remains holomorphic at the neighborhood of that point, we say that this point is a pole or an infinity of the function u.&quot; In the earlier paper, it's called &quot;an infinity of finite degree&quot;. http://mathoverflow.net/questions/44506/connective-constant-for-self-avoiding-walks-on-a-skip-chain Comment by Yuval Filmus Yuval Filmus 2010-11-07T05:19:01Z 2010-11-07T05:19:01Z I now have a complete proof that $\mu \approx 2.20556943040059$, following the steps of my answer below. http://mathoverflow.net/questions/45106/quantum-pcp-theorem Comment by Yuval Filmus Yuval Filmus 2010-11-07T00:23:52Z 2010-11-07T00:23:52Z That's probably more appropriate for cstheory.stackexchange.com http://mathoverflow.net/questions/44506/connective-constant-for-self-avoiding-walks-on-a-skip-chain/44532#44532 Comment by Yuval Filmus Yuval Filmus 2010-11-02T16:33:54Z 2010-11-02T16:33:54Z I should mention that both the initial list (of 6 &quot;ways&quot;) and the enumeration of the initial phase was compared against a brute-force enumeration of self-avoiding paths, so I expect it to be correct. It was also derived not in the haphazard way it may look like now. http://mathoverflow.net/questions/44506/connective-constant-for-self-avoiding-walks-on-a-skip-chain/44532#44532 Comment by Yuval Filmus Yuval Filmus 2010-11-02T16:32:36Z 2010-11-02T16:32:36Z Nor should it: I'm disregarding both the initial phase (which has polynomial multiplicative contribution) and some dead-end paths.