User vor - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T15:36:56Z http://mathoverflow.net/feeds/user/12875 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/86339/compression-of-a-turing-machine-run-sequence/129195#129195 Answer by Vor for compression of a Turing machine run sequence Vor 2013-04-30T09:01:58Z 2013-04-30T09:07:31Z <p>A <em>run sequence</em> $r = [s'_1a'_1,s'_2a'_2,s'_3a'_3,...]$, of a Turing machine $M$ on input $x$ is a highly compressible string:</p> <p>$$K(r) = K(\langle M, x, z \rangle) + c \leq |\langle M \rangle| + | x | + \log z + c'$$</p> <p>where $z$ is the number of steps of the run sequence.</p> http://mathoverflow.net/questions/128079/a-bit-of-primes A "bit" of primes Vor 2013-04-19T12:39:04Z 2013-04-19T19:43:01Z <p>Is there anything known/proved/conjectured about the distribution of:</p> <p>$$B(n) = \frac{(p_n-1)}{2} \bmod 2, \qquad p_n \mbox{ is the } n\mbox{-th prime}$$</p> <p>i.e. the bit 1 of the binary representation of the $n$-th prime number?</p> http://mathoverflow.net/questions/77907/constructive-lower-bounds-for-multicolor-ramsey-numbers Constructive lower bounds for multicolor Ramsey numbers Vor 2011-10-12T08:58:34Z 2012-07-10T16:58:46Z <p>The $k$-color <a href="http://mathworld.wolfram.com/RamseyNumber.html" rel="nofollow">Ramsey number</a> 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.</p> <p>I'm looking for results (<strong>if exist</strong>) that link together Ramsey numbers of increasing number of colors; in particular, <strong>constructive</strong> ways to prove lower bounds.</p> <p>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$</p> <p>Can you give me some results / references?</p> <p>(or results of the same type that applies to particular class of graphs, for example complete bipartite graphs)</p> http://mathoverflow.net/questions/11540/what-are-the-most-attractive-turing-undecidable-problems-in-mathematics/98261#98261 Answer by Vor for What are the most attractive Turing undecidable problems in mathematics? Vor 2012-05-29T08:55:08Z 2012-05-29T08:55:08Z <p>My favourite is related to the <a href="http://en.wikipedia.org/wiki/Kolmogorov_complexity" rel="nofollow">Kolmogorov Complexity</a> of a string:</p> <blockquote> <p>The problem of deciding if a string $s$ is compressible ($K(s) &lt;^? |s|$) is undecidable</p> </blockquote> http://mathoverflow.net/questions/77523/3x3-submatrix-with-only-0-or-1-entries 3x3 submatrix with only $0$ or $1$ entries Vor 2011-10-08T10:25:42Z 2011-10-08T16:43:12Z <p>I decided to <a href="http://math.stackexchange.com/questions/70619/submatrix-with-only-0-or-1-entries" rel="nofollow">cross-post</a> the question here from math.stackexchange.com because I got no answer from there.</p> <p>It is a quick question on bipartite Ramsey numbers (I'm not an expert on the subject, so perhaps the question is trivial).</p> <p>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 ?</p> <p>I found some articles with upper/lower bounds, but not a clear chart with the particular values I need.</p> http://mathoverflow.net/questions/55010/prime-factorization-of-n1 Prime factorization of n+1 Vor 2011-02-10T10:44:50Z 2011-02-24T18:09:05Z <p>If $n=\prod_{i=1}^{k} p_i^{e_i}$ is a prime factorization of integer $n$.</p> <blockquote>Is there a quick way to find the prime factorization of $n+1$?</blockquote> <p>Or the only way to do it is recalculating the whole factorization?</p> <p>Any references and/or articles on this problem?</p> http://mathoverflow.net/questions/129719/the-prime-real-numbers-and-their-applications Comment by Vor Vor 2013-05-05T14:26:43Z 2013-05-05T14:26:43Z I searched a &quot;?&quot; character but didn't find it; so what is the asked question? :-) http://mathoverflow.net/questions/129667/how-to-prove-a-conjecture-on-a-canonical-equivalent-of-factoring Comment by Vor Vor 2013-05-05T14:15:15Z 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 &quot;cost&quot; of delimiting the codes, one can consider valid this simpler representation, too: pick the binary representation of a number, then split it in an &quot;array&quot; assuming that every digit has a one on its left; so 360 = 101101000 becomes [01,0,000]. This representation except for n&lt;2 is strictly &quot;shorter&quot; (in your sense) than b(n). http://mathoverflow.net/questions/129667/how-to-prove-a-conjecture-on-a-canonical-equivalent-of-factoring Comment by Vor Vor 2013-05-04T21:28:15Z 2013-05-04T21:28:15Z What do you mean exactly with &quot;succinct representation for the factoring of n&quot;? 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, http://mathoverflow.net/questions/86339/compression-of-a-turing-machine-run-sequence/129195#129195 Comment by Vor Vor 2013-05-01T15:03:39Z 2013-05-01T15:03:39Z @vzn: yes, you can look at [this short introduction by Lance Fortnow](<a href="http://people.cs.uchicago.edu/~fortnow/papers/kaikoura.pdf" rel="nofollow">people.cs.uchicago.edu/~fortnow/papers/&hellip;</a>) http://mathoverflow.net/questions/86339/compression-of-a-turing-machine-run-sequence/129195#129195 Comment by Vor Vor 2013-04-30T15:03:36Z 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-&gt;1 1-&gt;0 transitions, crossing sections, ecc. ecc.); but obviously they all lead to the same highly compressible property. http://mathoverflow.net/questions/128079/a-bit-of-primes/128125#128125 Comment by Vor Vor 2013-04-20T10:17:41Z 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 <i>consecutive</i> &quot;bit #1&quot; sequences of length $l$ among the $p_i, i\leq n$? (perhaps it is worth a new question on mathoverflow :-) http://mathoverflow.net/questions/128079/a-bit-of-primes/128125#128125 Comment by Vor Vor 2013-04-19T22:13:09Z 2013-04-19T22:13:09Z @quid: nice answer, I'll read (and try to understand :-) the suggested papers!!! thanks http://mathoverflow.net/questions/128079/a-bit-of-primes Comment by Vor Vor 2013-04-19T16:14:37Z 2013-04-19T16:14:37Z @quid: according to some tests I made they seems to be &quot;powerful enough&quot; to pass random tests like &quot;diehard&quot; (starting from an initial random prime $p_i$) ... http://mathoverflow.net/questions/111690/rate-of-growth-of-prime-numbers Comment by Vor Vor 2012-11-06T23:06:38Z 2012-11-06T23:06:38Z @Jo&#235;l: well done, I didn't read the FAQ ... :( and asked the (super-trivial) question only to get a confirmation http://mathoverflow.net/questions/77907/constructive-lower-bounds-for-multicolor-ramsey-numbers Comment by Vor Vor 2011-10-12T08:59:24Z 2011-10-12T08:59:24Z I'm not an expert of Ramsey Theory, let me know if the question is too generic http://mathoverflow.net/questions/77523/3x3-submatrix-with-only-0-or-1-entries/77524#77524 Comment by Vor Vor 2011-10-08T16:46:18Z 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 &quot;not 15&quot; part) http://mathoverflow.net/questions/77523/3x3-submatrix-with-only-0-or-1-entries/77524#77524 Comment by Vor Vor 2011-10-08T16:26:45Z 2011-10-08T16:26:45Z Thank you! In the abstract of Irvin's paper available online (<a href="http://journals.cambridge.org/action/displayAbstract?fromPage=online&amp;aid=5046044" rel="nofollow">journals.cambridge.org/action/&hellip;</a>) he says that the result b(3,3)=17 <i>is from [1]</i> 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). http://mathoverflow.net/questions/77523/3x3-submatrix-with-only-0-or-1-entries/77524#77524 Comment by Vor Vor 2011-10-08T11:13:15Z 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. <i>Proc.5th British Combin. Conf. 1975, Congressus Numer.</i> XV (1975), 17-22. I would like to see his proof, but I didn't find that article online.