User yuval filmus - MathOverflow

Answer by Yuval Filmus for Beyond Hilton-Milner Theorem for an Intersecting Family?

2013-04-17T02:44:39Z

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 < 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").

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").

A third one is due to Dinur and Friedgut ("intersecting families are essentially contained in juntas"). For $k = cn$, they show that any intersecting family essentially depends on $O(1)$ points, where the constant depends on $c$. For $k = o(n)$, they can show that any intersecting family has an element common to all but $C \binom{n-2}{k-2}$ of the sets.

Padé approximations of $e$

2012-02-12T05:27:28Z

The following question came up in the analysis of some algorithm.

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} < r_{n,2} < \cdots < 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} < \cdots, $$ with equality when $n = 4k+1$. So the tightest lower and upper bounds appear in the middle of any secondary diagonal.

These properties of the sequence $r_{n,0},\ldots,r_{0,n}$ were observed experimentally. Why do they hold?

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?

(Using the explicit expression for the error term, it is easy to prove that $\bigcap_{n=2}^\infty I_n = \{e\}$.)

Frobenius norms of Fourier coefficients of the symmetric group

2011-03-09T03:24:15Z

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"?

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$.

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.

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))$?

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$)

Answer by Yuval Filmus for Big O notation and the maximal set of comparable functions

2010-11-10T04:47:20Z

There is no countable chain which is maximal: if $f_i$ is a sequence of functions, then define

$g(n) = n \cdot \max_{i \leq n} f_i(i)$

The function $g$ grows faster than all the functions in the sequence.

So there's probably no simple explicit construction other than the one obtained through transfinite induction.

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).

You can further ask what happens if the functions need to be recursive - that's the fast-growing hierarchy.

Answer by Yuval Filmus for Asymptotics for forbidden subwords

2010-11-07T17:54:48Z

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.

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.

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.

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\}$.

Edited to explain the acronyms re Bill's comment.

Answer by Yuval Filmus for Pseudonyms of famous mathematicians

2010-11-07T18:30:23Z

Felix Hausdorff published philosophical and literary books as Paul Mongré.

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).

Answer by Yuval Filmus for Connective constant for self-avoiding walks on a skip-chain

2010-11-02T09:36:21Z

A step is a movement of magnitude 1, a hop of magnitude 2.

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:

Hop left $n$ times and get stuck.
Step right to reach $E_0$.
Hop right, step left, hop right, reaching $E_0$.
Hop $m\geq 1$ times right, then step right, reaching $E_m$.
Hop $m\geq 2$ times right, step left, hop $m-1$ times left and get stuck.
Hop $m\geq 2$ times right, step left, then hop right, reaching $E_0$.

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$.

So we get from $E$ to $E$ by one of the following:

Step right.
Hop right, step left, hop right.
Hop $m \geq 1$ times right, step right.
Hop $m \geq 2$ times right, step left, hop right.

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

$1/(1-x-x^2-2x^3/(1-x)) = (1-x)/(1-2x-x^3)$

The denominator has one real root, about 0.453397651516404. So the $k$ term is $O(2.20556943040059^k)$.

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$.

When are infinitely many points in the orbit of a polynomial integers?

2010-10-28T01:45:34Z

This question is inspired by a riddle in math.stackexchange.

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?

We can ask the same question replacing integers with rationals.

EDIT: Nick and David gave simple counterexamples for the first question. Still open:

In the setting of the original question, is it true that some composition power of $P$ takes integers to integers?
The original question with rationals.

Answer by Yuval Filmus for Arithmetic of ordered sets more general than ordinals

2010-09-12T23:43:54Z

I recommend Rosenstein's excellent book "Linear orderings".

Notation for a graph without any edges?

2010-08-26T03:48:44Z

Is there a standard notation for a graph (on a given set of vertices) without any edges?

How many pairs of edges can disconnect a biconnected graph?

2010-08-17T04:26:28Z

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).

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.

Is the conjecture true? I have a candidate proof but I suspect that there's a simpler one.

Answer by Yuval Filmus for characterization of trees in terms of products of transpositions

2010-07-20T02:35:29Z

Notation: αβ means apply α then β.

If the graph is not a tree, then either it contains a cycle or it contains less than n−1 edges. In the latter case, we get a contradiction since less than n−1 transpositions cannot multiply to a big cycle.

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 π. So for each product σ of the edges of the cycle, πσ is a long cycle.

For each i<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).

Thus for each i<j, π(ij)τ is a big cycle, where τ does not involve i or j. In particular, π(i)≠j. Since this is true for all i≠j, it follows that π must be the identity. We get a contradiction since σ is not a big cycle.

Answer by Yuval Filmus for Motivation of Moment Generating Functions

2010-08-01T00:15:25Z

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.

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).

Answer by Yuval Filmus for Lower Bounds in Theoretical Computer Science

2010-07-24T06:14:09Z

Union-find data structures have an inverse-Ackermann lower bound Ω(n α(n)), see Wikipedia.

Answer by Yuval Filmus for Finding the largest integer describable with a string of symbols of predefined length

2010-07-22T04:15:52Z

Given a computable function f(n), the function g(n) = nf(n) is also computable and dominates it.

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.

So F can be neither computable nor non-computable. In classic logic we've reached a contradiction.

Another problem with your definition is that you might have incomparable functions, i.e. functions where the test is inconclusive.

When do cofinal chains of universal codings of the integers exist?

2010-07-19T02:23:32Z

Universal codings of integers

A (binary) coding of the integers is a prefix-free code of the natural numbers, whose codewords are non-decreasing in size. A coding is universal if it is short enough (log n + o(log n)), but that's not important.

Some examples:

The unary coding 0, 10, 110, ...; code length is n
Code first the length of the number in unary, then the number itself in binary; code length is about 2log n
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
...
Diagonalize the construction to get code length of log n + log log n + ... + 2log^* n
Continue this way through the constructible ordinals

The diagonalized code, known as the $\omega$-code, is due to Peter Elias.

A partial ordering of codes

The sequence of codes above are progressively better, in the following sense:

A coding a is better than a coding b if |b(n)| - |a(n)| tends to infinity.

There are some natural questions to ask:

Is there a best code?
If not, is there an optimal sequence of codes?

As it turns out, not only is there no best code, but given any sequence of codes, we can always find a code which is better than all of them; the proof from one of Hausdorff's papers (Untersuchungen über Ordnungtypen V from 1907) can be adapted to our setting.

Scales

The best thing that can be hoped for is a chain 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).

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.

Here are some pointers:

Hausdorff Gaps and Limits by Frankiewicz and Zbierski, which deals with the ordering f > g if f(n) > g(n) infinitely often.
Gaps in $\omega^\omega$ by Marion Scheepers, which deals with the ordering f > g if f(n) - g(n) tends to infinity.

In their settings, Hechler forcing can be used to produce worlds in which there is no scale.

Is the existence of scale (in the context of monotone codings of integers) independent of set theory?

Codings and series

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_i exists iff the sum $\sum 2^{-w_i}$ converges.

The reductions are most easily stated if we extend our posets with some equivalence relation. We then say that two posets are interlacing 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.

The following posets are interlacing:

Arbitrary (non-monotone) codes, with a < b if b is better than a, and a ~ b if |a(n)-b(n)| is bounded.
Convergent positive series, with a < b if b(n) = o(a(n)), and a ~ b if a(n) = O(b(n)) and b(n) = O(a(n)).
Divergent positive series (reverse definition of <).

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.

Effective and efficient codings

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.

This prompts us to ask similar questions for effective (computable) codings.

Can classical recursion theory hierarchies be adapted to the setting of codes?

It would be nice to get an analog of the fast-growing hierarchy, for example.

We could further wonder what happens if we ask our coding procedure to be efficient, for example linear-time computable.

Answer by Yuval Filmus for Does an "efficient" random number generator exist?

2010-07-21T03:49:47Z

I assume that n is a power of 2.

You can try an LFSR (check Wikipedia), but that will cycle (given the correct feedback) only over the non-zero integers in your range.

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.

Answer by Yuval Filmus for n-widths and Kolmogorov's entropy

2010-07-20T04:22:33Z

You can try An Introduction to Kolmogorov Complexity and Its Applications by Ming Li and Paul Vitányi, it's an excellent book.

Answer by Yuval Filmus for enumerative combinatorics with fixed number repeats

2010-07-20T01:28:52Z

Suppose we have n elements, we want to generate r elements (without order), and want exactly k elements to be repeated.

We can separate the result into a part containing all the repeated elements (the repeating part) and all the rest (the non-repeating part). Suppose the repeating part is of length m. 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 m−2k 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.

Putting it all together:

$\binom{n}{k} \sum_{m=2k}^r \binom{m-k-1}{k-1} \binom{n-k}{r-m}$

If you want to allow less repeating elements, just sum over k as well.

What is the limiting distribution of local minima of n mod i, for i up to $\sqrt{n}$, as $n \rightarrow \infty$?

2010-07-19T01:32:13Z

The sequence n mod i

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 < 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).

Local minima of the sequence

Now suppose we take only local minima of the sequence. If we do this, we get what look like dense triangles (beware: slowly loading!), with some outliers between the triangles. One explanation goes like this: $n \mod i = i \cdot frac(n/i)$; if i 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.

What is the limiting density (if any) of this sequence? How many outliers are there, asymptotically?

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}$.

Further iterations

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.

Answer by Yuval Filmus for A riddle about zeros, ones and minus-ones

2010-07-18T23:23:34Z

Another answer (I guess they must be equivalent):

Write each original line as a difference of two 0/1 vectors.
Adapt this representation to the modified lines by changing only the subtrahends.
You now have a function from {0,1}^n to {0,1}^n. Find a cycle.

Comment by Yuval Filmus

2012-02-12T18:16:35Z

The continued fraction expansion apparently involves only diagonal or near-diagonal elements. But formulas for the Padé approximants do appear in Perron's text on continued fractions.

Comment by Yuval Filmus

2011-08-15T20:22:16Z

Crossposted on math.stackexchange: math.stackexchange.com/questions/21230/…

Comment by Yuval Filmus

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$).

Comment by Yuval Filmus

2011-01-31T18:36:35Z

cross-posted in math.stackexchange: math.stackexchange.com/questions/19691/…

Comment by Yuval Filmus

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.

Comment by Yuval Filmus

2011-01-12T16:37:03Z

In fact, a language is circular iff it's the <i>union</i> of expressions of the form $r^*$.

Comment by Yuval Filmus

2011-01-12T16:35:53Z

Cross-posted on cstheory: cstheory.stackexchange.com/questions/4254/….

Comment by Yuval Filmus

2011-01-09T04:44:32Z

Some take it as part of the definition of "graph property".

Comment by Yuval Filmus

2010-11-14T00:30:22Z

Please repost in math.stackexchange.com .

Comment by Yuval Filmus

2010-11-10T04:49:37Z

Can't you add $f(x)=x$ to your set?

Comment by Yuval Filmus

2010-11-07T06:47:38Z

"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." In the earlier paper, it's called "an infinity of finite degree".

Comment by Yuval Filmus

2010-11-07T05:19:01Z

I now have a complete proof that $\mu \approx 2.20556943040059$, following the steps of my answer below.

Comment by Yuval Filmus

2010-11-07T00:23:52Z

That's probably more appropriate for cstheory.stackexchange.com

Comment by Yuval Filmus

2010-11-02T16:33:54Z

I should mention that both the initial list (of 6 "ways") 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.

Comment by Yuval Filmus

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.