User yuta suzuki - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T06:26:21Z http://mathoverflow.net/feeds/user/25386 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/103885/consecutive-integers-with-no-large-prime-factors Consecutive integers with no large prime factors Yuta Suzuki 2012-08-03T17:28:34Z 2013-01-10T21:15:07Z <p>I need answer of following Question for my study of an irrational number. (The raw problem is slightly different.)</p> <p>Let $k$ be an arbitrary large positive integer, and let $A$ is a positive integer satisfying $Ce^{2^k}\le A\le Ce^{2^k}$ and have no prime factor larger than $2^k$.(Conventionally, $C$'s are certain positive constants.) Let $y_0$ be a positive integer which suffices $y_0&lt; A$. We now think about $2^k$ products $$P_s=(y_0+As+1)(y_0+As+2)\cdots(y_0+As+k)\qquad (0\le s&lt; 2^k).$$ Question is "Can we find some $s$'s such that $P_s$ has no prime factor larger than $2^k$?". </p> <p>It is helpful not only answer for this question, but also introducing relating paper or research.(I can't discover relating research.)</p> <p>If this question is nonsense or ridicurous, sorry for asking this question.</p> <p>Sorry, I got some help which asserts some mistakes in my previous question.So probably, this question contains some mistakes. If you discover some of mistakes, it's helpful asserting that.</p> http://mathoverflow.net/questions/108164/small-ramsey-number-and-brooks-theorem small Ramsey number and Brooks' Theorem Yuta Suzuki 2012-09-26T13:45:00Z 2012-09-27T15:27:30Z <p>I'm studying about Graph Ramsey Theory now. Starting this study, I'm reading Chvatal and Harary's series of papers. In the second paper (V.Chvatal, F.Harary, Generalized ramsey theory for graphs,Ⅲ. Small off-diagonal numbers, Pacific Journal of Mathematics 41, No.2, 1972, pp.335-345), I can't understand the proof of $r(C_4,K_4)=10$. Their proof is like following.</p> <p>Let $G$ is arbitrary simple graph of order 10 with point independence number $&lt;4$. It is sufficient to prove $G$ contains $C_4$. From $G$'s point independence number is $&lt;4$, $G$'s (point) chromatic number is $\ge4$. Hence by Brooks' theorem either $K_4$ (and hence $C_4$) is contained in $G$, or the degree of each point of $G$ is at least four. If the first case occur, we have done. If the second case occur, we also have $C_4$ in $G$ by the following lemma (I omit the proof of this lemma but it's not so difficult). </p> <p>Lemma. If a graph $G$ with $p$ points has minimum degree $d$ and $d(d-1)>p-1$, then $G$ contains $C_4$.</p> <p>I can't understand how to use Brooks' Theorem. I only succeed to derive the maximum degree of $G$ is greater than 3. How to derive that the minimum degree of $G$ is greater than 3 from Brooks' Theorem? Chvatal and Harary's proof is wrong as it is? or not? (If you have other elegant proof of $r(C_4,K_4)=10$, then It also help me.)</p> <p>supplementation:I got a (awkward?) proof of $r(C_4,K_4)=10$. The proof is like following.</p> <p>For lower bound, we use Chvatal-Harary theorem.</p> <p>For upper bound, we think about above graph $G$. Using $r(C_4,K_3)=7$, easily we have there is no vertex with degree $\le2$. By lemma, we have at least one vertex (say $u$) whose degree is 3.</p> <p>Claim. The subgraph induced by vertices non-adjacent to $u$ contains $2K_3$.</p> <p>The subgraph induced by vertices non-adjacent to $u$ has 6 vertices. So we have two triangles $T_1,T_2$ in this subgraph. If $T_1,T_2$ has two common vertex, we get $C_4$. If $T_1,T_2$ has only one common point, let $T_j=v_0v_1^jv_2^j$. Let $w$ be the other vertex non-adjacent to $u$. Then $v_2^1w$ isn't an edge by symmetry and avoiding $C_4$, namely $v_0v_1^1wv_2^1$. We also have edge $v_1^2w$ by avoiding 4 independent vertices $v_2^1wv_1^2u$.By symmetry, we have $C_4$, namely $v_0v_1^2wv_2^2$ and it's a contradiction.</p> <p>Claim. The neighborhood subgraph $N(u)$ of $u$ is $\bar{K_3}$.</p> <p>If not, the neighborhood subgraph of $u$ is an isolated vertex $v_1$ and an edge $v_2v_3$. $v_2$ and $v_3$ has at least one edge to $T_1\cup T_2$, since their degree $\ge3$. If $v_2$ and $v_3$ has edges to common triangle, we get $C_4$. So if we let $T_j=w_1^jw_2^jw_3^j$, we can assume there are edges $v_2w_1^1, v_3w_1^2$. ($v_1,v_2$ has no other edges to $T_1\cup T_2$.) Then both edges $v_1w_2^1,v_1w_3^1$ cannnot be exist. So we can assume there isn't edge $v_1w_3^1$, then we have edge $w_3^1w_1^2$, since otherwise we have 4 independent vertices $v_1v_2w_3^1w_1^2$. By symmetry, we also have edge $w_1^1w_3^2$. So we have $C_4$, $w_1^1w_3^2w_1^2w_3^1$. It's a contradiction.</p> <p>Now, we have $T_j=w_1^jw_2^jw_3^j$ and 6 edges $v_iw_i^j$. Then we have edge $w_1^1w_1^2$, since otherwise $w_1^1w_1^2v_2v_3$ form 4 independent vertices. By symmetry, we have $C_4$, namely $w_1^1w_1^2w_2^2w_2^1$. It's a contradiction.</p> http://mathoverflow.net/questions/103376/an-estimate-of-the-sum-related-to-primes An estimate of the sum related to primes Yuta Suzuki 2012-07-28T11:13:07Z 2012-07-29T14:00:38Z <p>I can't solve following exercise in a note about prime numbers. I need this for study about large gaps of consecutive prime numbers.</p> <p>Prove that f $0&lt;1-\delta&lt;1$ then</p> <p>$$\sum_{p\le y}\frac{1}{p^{1-\delta}}\le\frac{y^\delta}{\log(y^\delta)}+\log(1/\delta)+O\left(\frac{y^\delta}{\delta(\log y)^2}+1\right)$$.</p> <p>In the note, a hint was given, that is "Split the sum at $p\le e^{2/\delta}$". How this estimate can be proven?</p> http://mathoverflow.net/questions/108164/small-ramsey-number-and-brooks-theorem/108204#108204 Comment by Yuta Suzuki Yuta Suzuki 2012-09-27T17:56:08Z 2012-09-27T17:56:08Z Then above Chvatal-Harary's proof is wrong? or not? How do you think about it? I want to know this mainly, so I can't let your answer accepted, but your answer is very helpful, so I voted up yours. http://mathoverflow.net/questions/108164/small-ramsey-number-and-brooks-theorem/108204#108204 Comment by Yuta Suzuki Yuta Suzuki 2012-09-27T17:53:45Z 2012-09-27T17:53:45Z Thank you very much for your edit. I was confused in &quot;Hence, $G[N(v)]$ must be a matching $ab,cd$ of size 2&quot; because I thought the case when c,d has two edges to $S(v)$. But by easy argument, this case can be excluded. And I can't understand (perhaps because of my weak ability of English) the sentence &quot;Thus, every other vertex of $H$ is a stable set in $G$&quot;. Does this means &quot;if let $C_8=v_1\dots v_8$, then $v_1v_3v_5v_7$ form stable set&quot;? Finally, by your kindly help, we got two proofs which one is avoids Brooks' theorem, the other avoids above lemma. (to be continue) http://mathoverflow.net/questions/108164/small-ramsey-number-and-brooks-theorem/108204#108204 Comment by Yuta Suzuki Yuta Suzuki 2012-09-27T04:56:14Z 2012-09-27T04:56:14Z Thank you very much. I'll add details my proof(?). Your proof is interesting to me. But I can't understand the sentence &quot;This implies that some vertex of $C$ has degree 2 in $G$, since $N(v)$ only contains four vertices, a contradiction. &quot;. Why there aren't no vertex in $N(v)$ which has two neighborhood in $S(v)$? Perhaps this is easy question, sorry. http://mathoverflow.net/questions/108164/small-ramsey-number-and-brooks-theorem Comment by Yuta Suzuki Yuta Suzuki 2012-09-27T03:54:19Z 2012-09-27T03:54:19Z Than you very much GH. I'm not good at English, so I did not know that convention. If you haven't warn me, I have disrespect to their for long time. http://mathoverflow.net/questions/103885/consecutive-integers-with-no-large-prime-factors/103889#103889 Comment by Yuta Suzuki Yuta Suzuki 2012-08-04T04:01:31Z 2012-08-04T04:01:31Z read your link to wikipedia, and I think stormer's theorem can be applied to finite sets of primes P. But in my question, the number of primes not greater than 2k tends to $\infty$ as $k\to\infty$. So perhaps stormer's theorem can not be applied to my question. Is it right? For bounds, I'm researching now. http://mathoverflow.net/questions/103885/consecutive-integers-with-no-large-prime-factors Comment by Yuta Suzuki Yuta Suzuki 2012-08-03T17:58:23Z 2012-08-03T17:58:23Z for Olsen, conventionally, $C$ can be different values at the different place. for quid, sorry, you're right. I must modify the question, but whole my study is too large to write here, so please give me some hours. p.s. I researched about smooth number little, but I don't get similar problem. http://mathoverflow.net/questions/103376/an-estimate-of-the-sum-related-to-primes Comment by Yuta Suzuki Yuta Suzuki 2012-07-31T04:07:52Z 2012-07-31T04:07:52Z I think spliting at e^{1/\delta} is perhaps easier to prove js's estimation $p^\delta=1+O(\delta\log p)$. Thank the answers very much. http://mathoverflow.net/questions/103376/an-estimate-of-the-sum-related-to-primes/103449#103449 Comment by Yuta Suzuki Yuta Suzuki 2012-07-31T04:04:10Z 2012-07-31T04:04:10Z Thank you so much. I couldn't notice $p^\delta=1+O(\delta\log p)$. http://mathoverflow.net/questions/103376/an-estimate-of-the-sum-related-to-primes/103437#103437 Comment by Yuta Suzuki Yuta Suzuki 2012-07-31T03:45:29Z 2012-07-31T03:45:29Z Thank you so much for your answer. I understand almost all your calculation, but I can't understand your estimation of integral $\int_{e^{2/\delta}}^y\frac{t}{\log t}t^{-2+\delta}dt$. I think this can be estimated by twice partial integration. Your estimation of this integral is like mine? Sorry for asking very easy question.