User vor - MathOverflow

Answer by Vor for compression of a Turing machine run sequence

2013-04-30T09:01:58Z

A run sequence $r = [s'_1a'_1,s'_2a'_2,s'_3a'_3,...]$, of a Turing machine $M$ on input $x$ is a highly compressible string:

$$K(r) = K(\langle M, x, z \rangle) + c \leq |\langle M \rangle| + | x | + \log z + c' $$

where $z$ is the number of steps of the run sequence.

A "bit" of primes

2013-04-19T12:39:04Z

Is there anything known/proved/conjectured about the distribution of:

$$B(n) = \frac{(p_n-1)}{2} \bmod 2, \qquad p_n \mbox{ is the } n\mbox{-th prime}$$

i.e. the bit 1 of the binary representation of the $n$-th prime number?

Constructive lower bounds for multicolor Ramsey numbers

2011-10-12T08:58:34Z

The $k$-color Ramsey number of the complete graph $K_n$, denoted with $R_k(n)$, is defined to be the smallest integer $t$, such that in any $k$-coloring of the edges of $K_t$, there is a complete subgraph $K_n$ all of whose edges have the same color.

I'm looking for results (if exist) that link together Ramsey numbers of increasing number of colors; in particular, constructive ways to prove lower bounds.

For example: suppose that we have an instance of $K_{r_1}$ that proves $R_{k_1}(n_1) \gt r_1$ then we can build an instance of $ K_{r_2}$ that proves $R_{k_2}(n_2) \gt r_2$ for some particular $k_2 \lt k_1$ and $n_2 \gt n_1$

Can you give me some results / references?

(or results of the same type that applies to particular class of graphs, for example complete bipartite graphs)

Answer by Vor for What are the most attractive Turing undecidable problems in mathematics?

2012-05-29T08:55:08Z

My favourite is related to the Kolmogorov Complexity of a string:

The problem of deciding if a string $s$ is compressible ($K(s) <^? |s| $) is undecidable

3x3 submatrix with only $0$ or $1$ entries

2011-10-08T10:25:42Z

I decided to cross-post the question here from math.stackexchange.com because I got no answer from there.

It is a quick question on bipartite Ramsey numbers (I'm not an expert on the subject, so perhaps the question is trivial).

What is the least positive integer $r$ such that, any $r \times r$ 0-1 matrix contains at least one $3 \times 3$ submatrix filled with only 0 or only 1 entries ?

I found some articles with upper/lower bounds, but not a clear chart with the particular values I need.

Prime factorization of n+1

2011-02-10T10:44:50Z

If $n=\prod_{i=1}^{k} p_i^{e_i}$ is a prime factorization of integer $n$.

Is there a quick way to find the prime factorization of $n+1$?

Or the only way to do it is recalculating the whole factorization?

Any references and/or articles on this problem?

Comment by Vor

2013-05-05T14:26:43Z

I searched a "?" character but didn't find it; so what is the asked question? :-)

Comment by Vor

2013-05-05T14:15:15Z

@PaulTarau: ok, now it's clear. But it is a kind of cheating, because if you don't take into account the "cost" of delimiting the codes, one can consider valid this simpler representation, too: pick the binary representation of a number, then split it in an "array" assuming that every digit has a one on its left; so 360 = 101101000 becomes [01,0,000]. This representation except for n<2 is strictly "shorter" (in your sense) than b(n).

Comment by Vor

2013-05-04T21:28:15Z

What do you mean exactly with "succinct representation for the factoring of n"? For every succinct representation $r(\cdot)$, and for every m there is a number $n$ whose binary representation has length $m =b(n)$ that is incompressible (i.e. $|r(n)|\geq b(n)$. See Kolmogorov complexity,

Comment by Vor

2013-05-01T15:03:39Z

@vzn: yes, you can look at [this short introduction by Lance Fortnow](people.cs.uchicago.edu/~fortnow/papers/…)

Comment by Vor

2013-04-30T15:03:36Z

@AndreasBlass: indeed it's not too different from Sawin's idea :( ... there are also other variants (consider only states, include head directions, 0->1 1->0 transitions, crossing sections, ecc. ecc.); but obviously they all lead to the same highly compressible property.

Comment by Vor

2013-04-20T10:17:41Z

@quid, @Greg Martin, I downloaded the papers and started to read the Prime Number Races (it seems the math version of a E.A.Poe novel :-)))) ); just another quick question (I'm definitively not an expert in number theory): given an arbitrary $p_n$ and an integer $l$ can we prove anything about the probability to find two equal consecutive "bit #1" sequences of length $l$ among the $p_i, i\leq n$? (perhaps it is worth a new question on mathoverflow :-)

Comment by Vor

2013-04-19T22:13:09Z

@quid: nice answer, I'll read (and try to understand :-) the suggested papers!!! thanks

Comment by Vor

2013-04-19T16:14:37Z

@quid: according to some tests I made they seems to be "powerful enough" to pass random tests like "diehard" (starting from an initial random prime $p_i$) ...

Comment by Vor

2012-11-06T23:06:38Z

@Joël: well done, I didn't read the FAQ ... :( and asked the (super-trivial) question only to get a confirmation

Comment by Vor

2011-10-12T08:59:24Z

I'm not an expert of Ramsey Theory, let me know if the question is too generic

Comment by Vor

2011-10-08T16:46:18Z

Ok, I found Irving's paper. I probably made an error in the symmetry breaking rules (and removed the update). Thank you, again. (you can remove the "not 15" part)

Comment by Vor

2011-10-08T16:26:45Z

Thank you! In the abstract of Irvin's paper available online (journals.cambridge.org/action/…) he says that the result b(3,3)=17 is from [1] and I suppose that [1] refers to Beineke's paper. Have you read the whole Irvin's paper and found the proof of the equality? (if yes I'll buy it).

Comment by Vor

2011-10-08T11:13:15Z

In Henning's article the b(3,3)=17 result is from L.W. Beineke and A.J. Schwenk, On a bipartite form of the Ramsey problem. Proc.5th British Combin. Conf. 1975, Congressus Numer. XV (1975), 17-22. I would like to see his proof, but I didn't find that article online.