User yuta suzuki - MathOverflow

Consecutive integers with no large prime factors

2012-08-03T17:28:34Z

I need answer of following Question for my study of an irrational number. (The raw problem is slightly different.)

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< 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< 2^k).$$ Question is "Can we find some $s$'s such that $P_s$ has no prime factor larger than $2^k$?".

It is helpful not only answer for this question, but also introducing relating paper or research.(I can't discover relating research.)

If this question is nonsense or ridicurous, sorry for asking this question.

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.

small Ramsey number and Brooks' Theorem

2012-09-26T13:45:00Z

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.

Let $G$ is arbitrary simple graph of order 10 with point independence number $<4$. It is sufficient to prove $G$ contains $C_4$. From $G$'s point independence number is $<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).

Lemma. If a graph $G$ with $p$ points has minimum degree $d$ and $d(d-1)>p-1$, then $G$ contains $C_4$.

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

supplementation:I got a (awkward?) proof of $r(C_4,K_4)=10$. The proof is like following.

For lower bound, we use Chvatal-Harary theorem.

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.

Claim. The subgraph induced by vertices non-adjacent to $u$ contains $2K_3$.

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.

Claim. The neighborhood subgraph $N(u)$ of $u$ is $\bar{K_3}$.

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.

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.

An estimate of the sum related to primes

2012-07-28T11:13:07Z

I can't solve following exercise in a note about prime numbers. I need this for study about large gaps of consecutive prime numbers.

Prove that f $0<1-\delta<1$ then

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

In the note, a hint was given, that is "Split the sum at $p\le e^{2/\delta}$". How this estimate can be proven?

Comment by Yuta Suzuki

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.

Comment by Yuta Suzuki

2012-09-27T17:53:45Z

Thank you very much for your edit. I was confused in "Hence, $G[N(v)]$ must be a matching $ab,cd$ of size 2" 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 "Thus, every other vertex of $H$ is a stable set in $G$". Does this means "if let $C_8=v_1\dots v_8$, then $v_1v_3v_5v_7$ form stable set"? Finally, by your kindly help, we got two proofs which one is avoids Brooks' theorem, the other avoids above lemma. (to be continue)

Comment by Yuta Suzuki

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 "This implies that some vertex of $C$ has degree 2 in $G$, since $N(v)$ only contains four vertices, a contradiction. ". Why there aren't no vertex in $N(v)$ which has two neighborhood in $S(v)$? Perhaps this is easy question, sorry.

Comment by Yuta Suzuki

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.

Comment by Yuta Suzuki

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.

Comment by Yuta Suzuki

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.

Comment by Yuta Suzuki

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.

Comment by Yuta Suzuki

2012-07-31T04:04:10Z

Thank you so much. I couldn't notice $p^\delta=1+O(\delta\log p)$.

Comment by Yuta Suzuki

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.