User p&#233;ter komj&#225;th - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T01:19:50Z http://mathoverflow.net/feeds/user/6647 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/131758/what-is-the-least-ordinal-than-cannot-be-embedded-in-mathbbr-mathbbr/131765#131765 Answer by Péter Komjáth for What is the least ordinal than cannot be embedded in $\mathbb{R}^\mathbb{R}$? Péter Komjáth 2013-05-24T19:39:03Z 2013-05-24T19:39:03Z <p>One can define an eventually increasing sequence <code>$\{f_\alpha:\alpha&lt;\omega_1\}$</code> by transfinite recursion on $\alpha$. By inserting sequences in the intervals $(f_\alpha(x),f_{\alpha+1}(x))$ we can see that $\omega_1$-sums (and of course, $\omega$-sums) do not lead out of the representable ordinals. This gives that all ordinals $&lt;\omega_2$ are representable and this is clearly sharp if CH holds, by Will's above answer. If CH fails, larger ordinals can be represented, if, e.g. Martin's Axiom holds. </p> http://mathoverflow.net/questions/130545/proof-of-the-weak-goldbach-conjecture/130547#130547 Answer by Péter Komjáth for Proof of the weak Goldbach Conjecture Péter Komjáth 2013-05-14T05:54:07Z 2013-05-14T05:54:07Z <p><a href="https://plus.google.com/114134834346472219368/posts/8qpSYNZFbzC" rel="nofollow">https://plus.google.com/114134834346472219368/posts/8qpSYNZFbzC</a></p> http://mathoverflow.net/questions/130447/collapsing-successor-of-singular/130453#130453 Answer by Péter Komjáth for collapsing successor of singular Péter Komjáth 2013-05-13T04:33:57Z 2013-05-13T04:33:57Z <p>I think this is a consequence of stationary forcing. See P. Larson: The Stationary Tower, p. 60. </p> http://mathoverflow.net/questions/127800/examples-of-stationary-set-preserving-forcings-that-are-not-semiproper/127812#127812 Answer by Péter Komjáth for Examples of stationary set preserving forcings that are not semiproper? Péter Komjáth 2013-04-17T08:56:26Z 2013-04-17T08:56:26Z <p>Namba forcing is stationary preserving but not semiproper unless Chang's Conjecture holds. See "Proper and Improper Forcing" of Shelah, Ch 12. </p> http://mathoverflow.net/questions/126916/countable-coloring-of-a-plane/126937#126937 Answer by Péter Komjáth for Countable coloring of a plane Péter Komjáth 2013-04-09T06:04:57Z 2013-04-09T10:49:33Z <p>This is a result of Erdos: Problems and results in chromatic graph theory, Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968) , pp. 27--35, Academic Press, New York, 1969, see p. 32. Available at the Renyi Institute's collection of Erdos papers: <a href="http://www.renyi.hu/~p_erdos/1969-13.pdf" rel="nofollow">http://www.renyi.hu/~p_erdos/1969-13.pdf</a> </p> <p>Here is the proof. Let $X$ be the graph on the plane where two points are joined iff their distance is rational. What we want to prove is that the graph has countable chromatic number. Instead, we prove that it has a well ordering in which each point is joined into finitely many smaller (by the well ordering) points. This done, it is easy to good color the vertices via a transfinite recursion along the well ordering. </p> <p>We prove the above statement for every $X\subseteq R^2$, by tranfinite induction on $|X|$. The case when $X$ is countable is obvious: order $X$ as the natural numbers. Assume that $\kappa=X$ is uncountable, and the statement is proved for every set $Y$ of cardinality less than $\kappa$. </p> <p>If $a\neq b$ are point of the plane, then let $F(a,b)$ denote the set of points in rational distance from both $a$ and $b$. It is easy to see that $F(a,b)$ is always countable. </p> <p>We can exhibit $X$ as the increasing, continuous union of subsets $\{X_\alpha:\alpha&lt;\kappa\}$ such that $X_0=\emptyset$, $|X_\alpha|&lt;\kappa$ and each $X_\alpha$ is closed under $F$. One way of seeing this is to enumerate $X$ as $\{x_\alpha:\alpha&lt;\kappa\}$ and let $X_\alpha$ be the closure of <code>$\{x_\beta:\beta&lt;\alpha\}$</code> under the operation $F$.<br> Now $X$ can partitioned into the difference sets $X_{\alpha+1}-X_\alpha$. Each set $X_{\alpha+1}-X_\alpha$ possesses a well ordering $\prec_\alpha$ as required and we define the well ordering of $X$ as follows: $x\prec y$ iff either $x\in X_{\alpha+1}-X_\alpha$ and $y\in X_{\beta+1}-X_\beta$ with $\alpha&lt;\beta$ or else $x \prec_\alpha y$ for some $\alpha$. </p> <p>We have to show that $\prec$ is as wanted, so let $a$ be a point. $a\in X_{\alpha+1}-X_\alpha$ for some $\alpha&lt;\kappa$.<br> We count those points $x$ which are joined to $a$ and $x\prec a$. Of these, only finitely many are in the $X_{\alpha+1}-X_\alpha$, as those precede $a$ by $\prec_\alpha$. The remaining points are in $X_\alpha$. But there can be only at most one point in $X_\alpha$ in rational distance from $a$, as otherwise, if say, $p,q\in X_\alpha$ are in rational distance from $a$, then $a\in F(p,q)\subseteq X_\alpha$, a contradiction. Altogether, we get finitely many plus one=finitely many points preceding $a$ and in rational distance from it. </p> http://mathoverflow.net/questions/103658/why-does-aleph-omega-have-more-than-aleph-omega-countable-subsets/103661#103661 Answer by Péter Komjáth for Why does $\aleph_{\omega}$ have more than $\aleph_{\omega}$ countable subsets? Péter Komjáth 2012-08-01T05:54:45Z 2012-08-01T05:54:45Z <p>Let <code>$\{A_\alpha:\alpha&lt;\omega_\omega\}$</code> be all countable subsets of $\omega_\omega$. We build one that is not among them, giving the contradiction. Pick $x_0\in\omega_1$ wich is not in <code>$\bigcup\{A_\alpha:\alpha&lt;\omega\}$</code>. Then choose $\omega_1\leq x_1&lt;\omega_2$ which is not in <code>$\bigcup\{A_\alpha:\alpha&lt;\omega_1\}$</code>, etc. Eventually we get a countable set <code>$\{x_0,x_1,\dots\}$</code> different from each $A_\alpha$. (This is essentially the argument for proving Konig's inequality.) </p> http://mathoverflow.net/questions/101870/is-every-set-class-generic-over-a-given-inner-model/101881#101881 Answer by Péter Komjáth for Is every set class generic over a given inner model? Péter Komjáth 2012-07-10T19:47:06Z 2012-07-10T19:47:06Z <p>Isn't it Theorem 15.46 in Jech's Set Theory (Springer 2003) book? Perhaps one can reformulate it as follows: every set is in some generic extension of HOD. </p> http://mathoverflow.net/questions/101348/minimal-blocks-for-a-family-of-finite-sets/101368#101368 Answer by Péter Komjáth for Minimal blocks for a family of finite sets Péter Komjáth 2012-07-05T06:43:32Z 2012-07-05T06:43:32Z <p>Dear Martin: I think you can easily extend the result for systems of infinite sets, where there is a set $A$ intersecting all sets in finitely many but at least 1 point. The latter property was investigated by Erdos and Hajnal in On a property of families of sets, Acta Math. Acad. Sci. Hungar. 12 (1961), 87--123, see <a href="http://www.renyi.hu/~p_erdos/1961-11.pdf" rel="nofollow">http://www.renyi.hu/~p_erdos/1961-11.pdf</a> Perhaps I also had some papers on this. Does this make any sense? </p> http://mathoverflow.net/questions/99227/sum-of-the-reciprocal-of-perfect-numbers/100482#100482 Answer by Péter Komjáth for Sum of the reciprocal of perfect numbers Péter Komjáth 2012-06-23T20:22:08Z 2012-06-23T20:22:08Z <p>There is, indeed a simple argument to show that the sum of the reciprocals of perfect numbers converges. It suffices to show that the number of perfect numbers up to $x$ is $O(\sqrt{x})$. As the number of even perfect numbers is less than $\log x$, it is enough to consider odd perfect numbers. Assume that $n\leq x$ is an odd perfetc number. If $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$, then $2n=(p_1^{\alpha_1}+p_1^{\alpha_1-1}+\cdots+1)(p_2^{\alpha_2}+p_2^{\alpha_2-1}+\cdots+1)\cdots(p_r^{\alpha_r}+p_r^{\alpha_r-1}+\cdots+1)$. As $n$ is odd, exactly one factor on the right hand side is even. As each $p_i$ is odd, the parity of the factor corresponding to $p_i$ is the same as the parity of $\alpha_i+1$, i.e., exactly one $\alpha_i$ is odd. That is, $n=p^\alpha N^2$, where $p$ does not divide $N$. It suffices to show that $N$ determines the prime power $p^\alpha$ and therefore for each $N^2\leq x$ there is only one odd perfect number of the above form. Now $$2=\frac{\sigma(n)}{n}=\left(1+\frac{1}{p}\cdots+\frac{1}{p^\alpha}\right)\frac{\sigma(N^2)}{N^2}$$ and so $$1+\frac{1}{p}+\cdots+\frac{1}{p^\alpha}=\frac{a}{b}$$ where $a/b$ is $2N^2/\sigma(N^2)$ in reduced form. As the denominator of the L.H.S. is $p^\alpha$, we must have $p^\alpha=b$.</p> http://mathoverflow.net/questions/99227/sum-of-the-reciprocal-of-perfect-numbers/99246#99246 Answer by Péter Komjáth for Sum of the reciprocal of perfect numbers Péter Komjáth 2012-06-10T16:48:51Z 2012-06-10T16:48:51Z <p>I think that Erdos proved in 1934 that the sum of the reciprocals of primitive abundant numbers is convergent. A number $n$ is abundant if $\sigma(n)\geq 2n$ and is primitive aboundant if it is aboundant but none of its proper divisor is. It is easy to see that perfect numbers are primitive aboundant and so is the result. P. Erdõs: On the density of the abundant numbers, J. London Math. Soc. 9 (1934), 278--282. Available as <a href="http://www.renyi.hu/~p_erdos/1934-04.pdf" rel="nofollow">http://www.renyi.hu/~p_erdos/1934-04.pdf</a> . </p> http://mathoverflow.net/questions/96891/ill-founded-recursion-without-fund/96895#96895 Answer by Péter Komjáth for "Ill-founded Recursion" without Fund Péter Komjáth 2012-05-14T13:30:29Z 2012-05-14T13:30:29Z <p>Let $x_0>x_1>\cdots$ be a strictly decreasing sequence in $(X,&lt;)$. We can define an $F$ which gives two solutions: $f_0$ which is 0 everywhere, and $f_1$, which has $f_1(y)=0$ if $y\le x_n$ for every $n$ and $f_1(y)=1$ if $y\ge x_n$ for some $n$. </p> http://mathoverflow.net/questions/92253/hales-jewett-theorem/92277#92277 Answer by Péter Komjáth for Hales Jewett Theorem Péter Komjáth 2012-03-26T14:37:40Z 2012-03-26T14:50:21Z <p>A simple application of the Hales-Jewett theorem give the following result: if $r$, $k$ are natural numbers, then there is a finite set $S$ of natural numbers which does not contain a $(k+1)$-AP, yet every coloring with $r$ colors gives a monochromatic $k$-AP. </p> <p>Let $N$ be sufficiently large. The HJ theorem says that if we color all sequences of length $N$, consisting of numbers between 0 and $k-1$, with $r$ colors, there is a monocolored combinatorial line, that is, a configuration of the form $f_0,\dots,f_{k-1}$, such that for a nonempty subset <code>$T\subseteq \{0,\dots,N-1\}$ $f_i$</code> is $i$ in $T$, and the same outside it. Now the set $S$ above consists of the sums $x_0+x_1M+x_2M^2+\cdots+x_{N-1}M^{N-1}$, ($0\leq x_j\leq k-1$), where $M$ is very large. That is, we map the HJ-hypercube via the mapping $(x_0,x_1,\dots,x_{N-1})\mapsto x_0+x_1M+x_2M^2+\cdots+x_{N-1}M^{N-1}$. If $M$ is large enough, then no linear combination with small ($\lt k$) coefficients that gives 0, unless the same linear combination gives 0 in the left hand side, i.e., in the hypercube, in which there is no $(k+1)$-AP. </p> http://mathoverflow.net/questions/92148/interesting-conjectures-discovered-by-computers-and-proved-by-humans/92171#92171 Answer by Péter Komjáth for Interesting conjectures "discovered" by computers and proved by humans? Péter Komjáth 2012-03-25T14:32:55Z 2012-03-25T14:32:55Z <p>Lovasz told me the following interesting story. He had read a paper containing a long list of computer generated conjectures, did not like most them, but suddenly found one, which turned out to be an interesting and deep question. Then he realized that the same question had been asked earlier by humans. See <a href="http://oldwww.cs.elte.hu/~lovasz/berlin.pdf" rel="nofollow">http://oldwww.cs.elte.hu/~lovasz/berlin.pdf</a>. </p> http://mathoverflow.net/questions/47384/the-history-of-proper-forcing/91533#91533 Answer by Péter Komjáth for The history of Proper Forcing Péter Komjáth 2012-03-18T14:19:26Z 2012-03-18T14:19:26Z <p>What I remember is that first Laver solved the Borel conjecture by an countable support iteration which added a real at every stage (1976). That such an iteration can be of any use, was very surprising at the time. Then Baumgartner introduced the very general notion of property A, which included most (all?) standard forcings known then which added reals and showed that countable support iteration of them behaves nicely (1978). Then came Shelah, who gave the proper definition (1980). This was again a surprising thing, as Baumgartner's definition was combinatorial (containing combinatorial properties of the poset, eh, almost) while Shelah simply required that P should preserve all stationary subsets of all sets of the form $[A]^{\aleph_0}$, that is, a semantic definition. Notice that Shelah's new theory gave new and elegant proofs to old theorems, as Baumgartner's consistency of that any two $\aleph_1$-dense sets of reals are isomorphic or Mitchell's consistency of the tree property of $\aleph_2$. </p> http://mathoverflow.net/questions/91182/tp-omega-2-and-the-continuum/91298#91298 Answer by Péter Komjáth for TP($\omega_2$) and the continuum Péter Komjáth 2012-03-15T14:49:52Z 2012-03-15T14:49:52Z <p>I think Spencer Unger in "Fragility and indestructibility of the tree property" proves that if one adds an arbitrary number of Cohen reals to Mitchell's model, then the tree property survives (see <a href="http://www.math.cmu.edu/~sunger/" rel="nofollow">http://www.math.cmu.edu/~sunger/</a>). </p> http://mathoverflow.net/questions/67436/is-there-any-sequence-a-n-of-nonnegative-numbers-for-which-sum-n-geq-1a-n/85559#85559 Answer by Péter Komjáth for Is there any sequence $a_n$ of nonnegative numbers for which $\sum_{n \geq 1}a_n^2 <\infty$ and $\sum_{n \geq 1}\left(\sum_{k \geq 1}\frac{a_{kn}}{k}\right)^2=\infty$? Péter Komjáth 2012-01-13T07:07:57Z 2012-01-13T07:07:57Z <p>In the recent issue of Matematikai Lapok, the report on the Schweitzer contest attributes the problem to Zoltan Buczolich and Julien Bremont. </p> http://mathoverflow.net/questions/82642/well-ordered-cofinal-subsets/82703#82703 Answer by Péter Komjáth for Well-ordered cofinal subsets Péter Komjáth 2011-12-05T13:45:40Z 2011-12-05T13:45:40Z <p>Nice argumant. BTW Hausdorff's name must be mentioned, who proved a stronger form of the statement and who started the investigation of ordered sets in general. </p> http://mathoverflow.net/questions/79565/forcing-the-nonexistence-of-a-certain-set/79618#79618 Answer by Péter Komjáth for Forcing the nonexistence of a certain set Péter Komjáth 2011-10-31T12:43:54Z 2011-10-31T12:43:54Z <p>Jech's book has a current reprint, so it can be bought. </p> http://mathoverflow.net/questions/78751/name-for-the-ground-model/78765#78765 Answer by Péter Komjáth for "name" for the ground model Péter Komjáth 2011-10-21T13:45:23Z 2011-10-21T13:45:23Z <p>In most cases, however, you can get rid of the problem of referring to $\check{M}$. Andreas' formula above, for example, can be written as $$(\forall D)((D\in \check{X})\Longrightarrow (D\cap \dot{G}\neq\emptyset)).$$ where $X$ is the set of dense subsets of $P$ (as defined in $M$). </p> <p>Another standard trick to ensure that $M$ is a definable class in $M[G]$ is to force over $L$ (whenever one can, this clearly rules out the use of some large cardinals). </p> http://mathoverflow.net/questions/76428/forcing-over-models-without-the-axiom-of-choice/76440#76440 Answer by Péter Komjáth for Forcing over models without the axiom of choice Péter Komjáth 2011-09-26T17:54:21Z 2011-09-26T17:54:21Z <p>Arnie Miller's "Long Borel hierarchies" specifically pp 8-12 may be of interest for you. See <a href="http://www.math.wisc.edu/~miller/res/longbor.pdf" rel="nofollow">here</a></p> http://mathoverflow.net/questions/72259/partitioning-mathbbr-into-aleph-1-borel-sets/72274#72274 Answer by Péter Komjáth for Partitioning $\mathbb{R}$ into $\aleph_1$ Borel sets Péter Komjáth 2011-08-07T07:17:00Z 2011-08-07T13:42:17Z <p>There is a Hausdorff gap, a sequence <code>$\{f_\alpha,g_\alpha:\alpha\lt\omega_1\}$</code> of $\omega\to\omega$ functions such that $f_\alpha\lt^*f_\beta&lt;^*g_\beta&lt;^*g_\alpha$ hold for $\alpha\lt\beta\lt\omega_1$ (here $f\lt^* g$ denotes eventual dominance, i.e., that $f(n)\lt g(n)$ holds for large $n\lt\omega$) and there is no function $f:\omega\to\omega$ such that $f_\alpha\lt^* f\lt^* g_\alpha$ holds for $\alpha\lt\omega_1$. If we identify the reals with ${}^\omega\omega$ and set <code>$H_\alpha=\{f:f_\alpha\lt^* f \lt^* g_\alpha\}$</code> then <code>$\{H_\alpha:\alpha\lt\omega_1\}$</code> is a decreasing sequence of nonempty $F_\sigma$ with empty intersection. </p> http://mathoverflow.net/questions/71983/more-on-lebesgue-non-measurability/71993#71993 Answer by Péter Komjáth for More on Lebesgue non-measurability Péter Komjáth 2011-08-03T13:06:32Z 2011-08-03T13:06:32Z <p>I have a construction which is probably overkill, but may be flexible enough to answer the "real" question (whatever that is). Let $A$ be a measure-zero planar set which meets all lines in continuum many points. (It is easy to find, e.g., take the union of countably many products of the interval and the Cantor-set) We select a subset $B\subseteq A$ such that all projections of $B$ are Bernstein sets (a set on a line is Bernstein if neither it nor its complement contains a perfect set). Enumerate all pairs consisting of a line $L$ and a perfect set $P$ on $L$ as <code>$\{(L_\alpha,P_\alpha):\alpha&lt;2^\omega\}$</code>. At step $\alpha$ we choose a point $x_\alpha$ and a line $M_\alpha$ with the intention of promising $x_\alpha\in B$ and $B\cap M_\alpha=\emptyset$. Assume we arrived at step $\alpha$. We have some less than continuum many points <code>$\{x_\beta:\beta&lt;\alpha\}$</code> which are promised into $B$, and some less than continuum many lines, which are promised to be disjoint from $B$. We are given a line $L_\alpha$ and a perfect set $P_\alpha$ on it. Choose a point $z$ in $P_\alpha$ which is not the projection of some $x_\beta$ (possible, as $P_\alpha$ has cardinality continuum, and less than that many points have been chosen). Erect a line on $z$, perpendicular to $L_\alpha$, that will be $M_\alpha$. Next, choose an element $y\neq z$, $y\in P_\alpha$ such that the line $K$ throu $y$, perpendicular to $L_\alpha$ is not one of the $M_\beta$'s ($\beta&lt;\alpha$). Then we can choose $x_\alpha\in K$ such that it is not in any of the lines $L_\beta$ ($\beta\leq\alpha$). Finally, $B={x_\alpha:\alpha&lt;2^\omega}$ is as required. </p> http://mathoverflow.net/questions/63600/size-of-stationary-sets/71750#71750 Answer by Péter Komjáth for Size of stationary sets Péter Komjáth 2011-07-31T18:54:24Z 2011-07-31T18:54:24Z <p>Shelah proved using his pcf theory that the least cardinality of a stationary subset of $P_\kappa(\lambda)$ is equal to the least cardinality of a cofinal subset of $P_\kappa(\lambda)$. See here: M. Shioya: A proof of Shelah's strong covering theorem for $P_\kappa(\lambda)$, Asian J. Math, 12(2008), 83-98.</p> http://mathoverflow.net/questions/68533/on-the-independence-of-the-kurepa-hypothesis/71748#71748 Answer by Péter Komjáth for On the independence of the Kurepa Hypothesis Péter Komjáth 2011-07-31T18:34:37Z 2011-07-31T18:34:37Z <p>This paper contains several results of the kind: Keith Devlin: $\aleph _{1}$-trees, Ann. Math. Logic 13(1978), 267–330. </p> http://mathoverflow.net/questions/71672/dual-covering-theorem/71719#71719 Answer by Péter Komjáth for Dual covering theorem Péter Komjáth 2011-07-31T09:39:18Z 2011-07-31T09:39:18Z <p>Perhaps Magidor's covering lemma may be mentioned: if $0^\sharp$ does not exist and $A$ is a set of ordinals which is closed under the primitive recursive set functions, then $A$ is the union of countably many constructible sets. M. Magidor: Representing sets of ordinals..., Transactions of the AMS, 317(1990), 91-126.</p> http://mathoverflow.net/questions/71565/partition-calculus-question/71570#71570 Answer by Péter Komjáth for Partition calculus question Péter Komjáth 2011-07-29T12:45:22Z 2011-07-29T12:45:22Z <p>I think that the general conjecture $\omega_1\to(\alpha,n)^3$ goes back to Erdos and Rado. </p> http://mathoverflow.net/questions/70347/successive-nth-powers-mod-p/70483#70483 Answer by Péter Komjáth for Successive nth powers mod p? Péter Komjáth 2011-07-16T05:31:13Z 2011-07-16T06:53:56Z <p>I think van der Waerden's theorem gives at least an arithmetic progression (not consecutive elements) consisting of $n$-th powers. Let $k,n$ be given and $p$ a sufficiently large prime. If $g$ is a primitive root mod $p$, then consider the following coloring of the reduced residue system: $x\mapsto c$ if $x\equiv g^{ny+c}\pmod{p}$ for some $y$ and $0\leq c \lt n$ . This is a coloring of $0,1,\dots,p-1$ with $n$ colors. By van der Waerden's theorem, there is an AP of length $k$, i.e., $y,y+H,\dots,y+(k-1)H$ get the same color, $c$. If we divide by $g^c$, we get an AP $z,z+h,\dots,z+(k-1)h$ of length $k$, consisting $n$-th powers. </p> http://mathoverflow.net/questions/59531/about-solvable-groups/59673#59673 Answer by Péter Komjáth for About solvable groups Péter Komjáth 2011-03-26T18:19:05Z 2011-03-26T18:19:05Z <p>The minimal non-solvable group surely has the property that all proper subgroups are solvable. </p> http://mathoverflow.net/questions/52318/is-there-always-for-a-given-prime-p-a-prime-ellp-that-is-not-a-quadratic/52385#52385 Answer by Péter Komjáth for Is there always, for a given prime $p$, a prime $\ell<p$ that is not a quadratic residue mod $p$? Péter Komjáth 2011-01-18T06:38:36Z 2011-01-18T06:38:36Z <p>Erdos conjectured that for any sufficiently large prime $p$ there is a primitive root <code>$q&lt;p$</code> for $p$ which is prime. </p> http://mathoverflow.net/questions/50428/determine-the-n-1th-fibonacci-number-from-a-given-extremely-large-nth/50436#50436 Answer by Péter Komjáth for Determine the (N-1)th fibonacci number from a given extremely large Nth ? Péter Komjáth 2010-12-26T16:38:41Z 2010-12-26T16:38:41Z <p>The n-th Fibonacci number can be calculated in log n steps, see, e.g., <a href="http://pages.cs.wisc.edu/~mhock/SSL/fibcalc.pdf" rel="nofollow">here</a></p> http://mathoverflow.net/questions/131221/yitang-zhangs-preprint-on-landau-siegel-zeros Comment by Péter Komjáth Péter Komjáth 2013-05-20T13:39:52Z 2013-05-20T13:39:52Z Good point. . http://mathoverflow.net/questions/130768/cardinals-without-choice-interpolation-reference-wanted Comment by Péter Komjáth Péter Komjáth 2013-05-16T03:41:54Z 2013-05-16T03:41:54Z I just heard this nice result from Fred Galvin a few weeks ago. My understanding is that he proved it without knowing a reference. http://mathoverflow.net/questions/128433/resources-on-wolstenholmes-theorem Comment by Péter Komjáth Péter Komjáth 2013-04-23T05:08:23Z 2013-04-23T05:08:23Z Did you try Dickson's &quot;Theory of Numbers&quot;? http://mathoverflow.net/questions/119355/compactness-of-the-hilbert-cube-without-the-axiom-of-choice/119374#119374 Comment by Péter Komjáth Péter Komjáth 2013-01-21T09:50:36Z 2013-01-21T09:50:36Z Similarly to Andrej's argument above, one can give an AC-free proof of the following result: if $X$ is a countable graph, every finite subgraph of $X$ has a good coloring with $k$ colors ($k$ is finite) then so has $X$. http://mathoverflow.net/questions/118959/axiom-of-choice-and-number-theory Comment by Péter Komjáth Péter Komjáth 2013-01-15T12:41:57Z 2013-01-15T12:41:57Z Hindman's theorem has a proof using Zorn's lemma. See, e.e., here: <a href="http://www.math.toronto.edu/lgoldmak/Hindman.pdf" rel="nofollow">math.toronto.edu/lgoldmak/Hindman.pdf</a> http://mathoverflow.net/questions/107163/a-function-that-is-defined-everywhere-but-has-unknown-values/107167#107167 Comment by Péter Komjáth Péter Komjáth 2012-09-14T21:34:53Z 2012-09-14T21:34:53Z The above &quot;joke&quot; is a famous comment made by Erdos on the above diagonal Ramsey numbers (somewhat loosely told). http://mathoverflow.net/questions/105400/extending-an-assignment-property-from-q-to-r-or-c/105404#105404 Comment by Péter Komjáth Péter Komjáth 2012-08-24T19:10:48Z 2012-08-24T19:10:48Z This problem, with the above solution, can be found in my book: Problems and solutions in classical set theory with Totik, in the chapter on Hamel bases as problem 15.23. http://mathoverflow.net/questions/103285/gods-book-of-paul-erds Comment by Péter Komjáth Péter Komjáth 2012-07-27T12:45:38Z 2012-07-27T12:45:38Z Erdos rather called it &quot;the transfinite book&quot;. He was certainly aware that proofs cannot be compared by elegance, that sometimes an ugly proof is &quot;the right one&quot;, that there is no such thing as the ultimate proof of a theorem. This was just a figure of speech used mostly when somebody gave a surprising new proof of a theorem. http://mathoverflow.net/questions/101870/is-every-set-class-generic-over-a-given-inner-model/101881#101881 Comment by Péter Komjáth Péter Komjáth 2012-07-10T20:01:41Z 2012-07-10T20:01:41Z Sorry, I don't know. http://mathoverflow.net/questions/96960/is-there-a-statement-equivalent-to-a-sentence-admitting-alphan-alpha Comment by Péter Komjáth Péter Komjáth 2012-05-15T04:36:19Z 2012-05-15T04:36:19Z Does $2^\alpha\geq\alpha^{+n}$ qualify? http://mathoverflow.net/questions/95056/consistency-and-inaccessible-cardinals Comment by Péter Komjáth Péter Komjáth 2012-04-24T19:09:50Z 2012-04-24T19:09:50Z What exactly are your questions? http://mathoverflow.net/questions/92291/von-mangoldt-pnt-and-zeta Comment by Péter Komjáth Péter Komjáth 2012-03-26T18:04:28Z 2012-03-26T18:04:28Z The fact that no zeta roots have zero as real part follows from that no roots have 1 as real part via the functional equation. http://mathoverflow.net/questions/92253/hales-jewett-theorem/92277#92277 Comment by Péter Komjáth Péter Komjáth 2012-03-26T15:56:51Z 2012-03-26T15:56:51Z Thanks, Andres. I could never figure that out... http://mathoverflow.net/questions/92148/interesting-conjectures-discovered-by-computers-and-proved-by-humans/92171#92171 Comment by Péter Komjáth Péter Komjáth 2012-03-26T05:23:05Z 2012-03-26T05:23:05Z Yes, exactly that one. http://mathoverflow.net/questions/92137/clarifying-erdos-conjecture-on-arithmetic-progressions Comment by Péter Komjáth Péter Komjáth 2012-03-25T06:04:49Z 2012-03-25T06:04:49Z The conjecture does not claim that $A$ is entirely composed of arithmetic progressions (unless we allow APs of length 1 or 2).