Tchebyshev theorem

[passer-by]

อยากได้วิธีพิสูจน์ว่า
$ \sqrt[n]{(n^{2})!} $ ไม่เป็นจำนวนเต็ม ทุก nณ2 ที่ไม่ใช้ Tchebyshev theorem(มีจำนวนเฉพาะอย่างน้อย 1 ตัวระหว่าง n กับ 2n) มาช่วยครับ

ขอบคุณล่วงหน้าสำหรับคำตอบครับ

[warut]

คุณ passer-by นี่ช่างสรรหาโจทย์ยากๆมาได้เสมอเลย คราวนี้ไปเอามาจากไหนอีกล่ะครับ

ถ้า $n\ne0$ เป็นจำนวนเต็ม และ $r$ เป็นจำนวนเต็มที่มากที่สุดที่ $2^r|\,n$ แต่ $2^{r+1}\not|\,n$ (นั่นคือ $2^r\|\,n$) แล้วเราจะเรียก $r$ ว่าเป็น 2-adic value ของ $n$ และเขียนแทนด้วยสัญลักษณ์ $v_2(n)$

จากสูตรของ Legendre เรารู้ว่า$$v_2(n!)= \sum_{i=1}^\infty \bigg\lfloor \frac{n}{2^i} \bigg\rfloor$$ถ้าเราเขียน $n$ ในรูป $n=a_k2^k+ a_{k-1}2^{k-1}+ \dots+ a_12^1 +a_0$ โดยที่ $2^k\le n <2^{k+1}$ และ $a_0,a_1,\dots,a_k$ มีค่าเป็น 0 หรือ 1 แล้วเราจะพบว่า$$v_2(n!)= n- (a_0+ a_1+ \dots+ a_k)= n- b(n)$$โดยที่ $b(n)$ คือจำนวนของบิท 1 ใน binary representation ของ $n$

ให้สังเกตว่า $b(n)\le k+1\le 1+\log_2n$

เราสามารถพิสูจน์ข้อความในโจทย์ได้โดยการแสดงว่า $n\not| \, v_2((n^2)!)$ เมื่อ $n\ge2$

จาก $v_2((n^2)!)= n^2-b(n^2)$ ดังนั้นเราจึงต้องการแสดงว่า $n\not| \,b(n^2)$ เมื่อ $n\ge2$

ในกรณีที่ $n=2,3,\dots,6$ เราจะเห็นว่า $n\not| \,b(n^2)$ จริง

ในกรณีที่ $n\ge7$ เราจะพิสูจน์ว่า $n\not| \,b(n^2)$ โดยการแสดงว่า $b(n^2)<n$ ดังนี้

จาก $b(n^2)\le 1+\log_2n^2$ ดังนั้นเราจึงต้องการแสดงว่า เมื่อ $n\ge7$ แล้ว $1+\log_2n^2<n$ นั่นคือการแสดงว่า $n^2<2^{n-1}$ ซึ่งสามารถทำได้โดยใช้ induction ครับ

[passer-by]

OH ! ขอบคุณคุณ warut มากๆๆๆๆครับ

ตอนที่ผม post ข้อความขณะนี้ ผมยังไม่ได้อ่าน คำตอบคุณ warut อย่างละเอียดหรอกครับ แต่รู้สึกว่า มันจะยากกว่าแบบที่ใช้ Tchebyshev theorem มาช่วย หลายเท่าตัวมากๆ

เอาไว้ให้อ่านแบบละเอียดๆ เสร็จแล้วมีอะไรสงสัย จะมาถามอีกทีนะครับ

ส่วนเรื่องที่มาของคำถามข้อนี้ อยากจะบอกว่า เป็นแค่การพิสูจน์ lemma ของโจทย์เท่านั้นครับ โจทย์จริงๆ คือ

กำหนดให้ nณ2 จงแสดงว่า ไม่สามารถ วางเลข 1,2,3,...,n² ลงใน จัตุรัส nxn โดยผลคูณสมาชิกทุกแถวหรือทุกหลักเท่ากันได้

ส่วนsource ของปัญหานี้ ผมไม่รู้จริงๆครับว่า original มาจากไหน แต่ที่ได้มานั้น เป็นปัญหาข้อ 44ที่ Prof. Yang Wang รวบรวมมาจากหลายๆที่ครับ

P.S. เห็นบ่นว่ายากยังไง ก็เรียบร้อยโรงเรียนคุณ Warut ทุกทีไม่ใช่หรือครับ

[TOP]

ไม่เกี่ยวกับโจทย์นะครับ แค่สงสัยว่า เวลากล่าวถึง xxx theorem มันไม่จำเป็นต้องหมายถึง theorem อันเดียวกันใช่ไหมครับ

เพราะผมเคยได้ยิน Tchebyshev theorem มาก่อนในเรื่องของพื้นที่ใต้เส้นโค้งปกติ (เรื่องอื่นผมก็เคยได้ยิน แต่ไม่แน่ใจว่าเรียกสั้นๆว่า Tchebyshev theorem หรือไม่)

หรือว่ามันมีการยกเว้นหาก xxx เป็นชื่อบุคคล ก็จะกล่าวสั้นๆว่าเป็น xxx theorem ส่วนจะเป็น theorem อันไหนของนาย xxx ก็เป็นที่รู้กันว่ากำลังคุยเรื่องอะไรกันอยู่

[warut]

ข้อความเดิมของคุณ passer-by:
ตอนที่ผม post ข้อความขณะนี้ ผมยังไม่ได้อ่าน คำตอบคุณ warut อย่างละเอียดหรอกครับ แต่รู้สึกว่า มันจะยากกว่าแบบที่ใช้ Tchebyshev theorem มาช่วย หลายเท่าตัวมากๆ

ถ้าใช้ Chebyshev Theorem จะง่ายกว่าเยอะครับ แต่ถ้าคำนึงถึงที่มาของ Chebyshev Theorem ด้วย วิธีที่ผมใช้นี่จะง่ายกว่ามากครับ เพราะใช้แค่ความรู้พื้นฐานเท่านั้น แต่ผมก็ยังไม่รู้ว่ามีวิธีอื่นที่ดีกว่าของผมรึเปล่านะ

ถ้าใช้ Chebyshev Theorem จะเป็นการ attack ที่ large prime factor ตัวนึงของ $(n^2)!$ ว่ามันมีอยู่ซ้ำกันน้อยครั้งเกินกว่าจะฟอร์มเป็น perfect $n^{\text{th}}$ power ได้

แต่แบบที่ผมทำจะ attack ที่ smallest prime factor นั่นคือ 2 โดยแสดงว่ามันมีอยู่ซ้ำกันเป็นจำนวนครั้งที่ไม่ใช่ multiple ของ $n$ ครับ

ข้อความเดิมของคุณ passer-by:
ส่วนเรื่องที่มาของคำถามข้อนี้ อยากจะบอกว่า เป็นแค่การพิสูจน์ lemma ของโจทย์เท่านั้นครับ โจทย์จริงๆ คือ

กำหนดให้ nณ2 จงแสดงว่า ไม่สามารถ วางเลข 1,2,3,...,n² ลงใน จัตุรัส nxn โดยผลคูณสมาชิกทุกแถวหรือทุกหลักเท่ากันได้

แต่ถ้าพิสูจน์ lemma นี้ได้แล้วที่เหลือก็จะตามมาทันทีเลยใช่มั้ยครับ

สมมติให้ผลคูณของแต่ละแถวเป็น $x$ ดังนั้นผลคูณของทุกแถวรวมกันจึงเป็น $x^n= (n^2)!$ แต่จากที่พิสูจน์ข้างบน เรารู้ว่า $(n^2)!$ ไม่เป็น perfect $n^{\text{th}}$ power เมื่อ $n\ge2$ เราจึงสรุปได้ว่าไม่มีจัตุรัสเช่นนั้นอยู่จริง

ข้อความเดิมของคุณ passer-by:
ส่วนsource ของปัญหานี้ ผมไม่รู้จริงๆครับว่า original มาจากไหน แต่ที่ได้มานั้น เป็นปัญหาข้อ 44ที่ Prof. Yang Wang รวบรวมมาจากหลายๆที่ครับ

อ๋อ เห็นแล้วครับ เป็น Problem 44 นั่นเอง เท่าที่ดูโจทย์ในนั้นมีแต่ยากๆทั้งนั้นเลย

สำหรับข้อนี้ผมก็ลองทำเป็นสิบวิธีน่ะครับ กว่าจะทำได้ พยายามมองหาทฤษฎีง่ายๆที่บอกถึง density, distribution หรือ gap ของจำนวนเฉพาะ ใช้คอมพ์เพื่อมองหา pattern จนสุดท้ายมาออกที่ 2-adic valuation นี่แหละครับ

ข้อความเดิมของคุณ TOP:
ไม่เกี่ยวกับโจทย์นะครับ แค่สงสัยว่า เวลากล่าวถึง xxx theorem มันไม่จำเป็นต้องหมายถึง theorem อันเดียวกันใช่ไหมครับ

เพราะผมเคยได้ยิน Tchebyshev theorem มาก่อนในเรื่องของพื้นที่ใต้เส้นโค้งปกติ (เรื่องอื่นผมก็เคยได้ยิน แต่ไม่แน่ใจว่าเรียกสั้นๆว่า Tchebyshev theorem หรือไม่)

หรือว่ามันมีการยกเว้นหาก xxx เป็นชื่อบุคคล ก็จะกล่าวสั้นๆว่าเป็น xxx theorem ส่วนจะเป็น theorem อันไหนของนาย xxx ก็เป็นที่รู้กันว่ากำลังคุยเรื่องอะไรกันอยู่

ก็น่าจะเป็นอย่างที่คุณ TOP ว่าตอนท้ายมั้งครับ

Chebyshev Theorem อันนี้บางทีก็เรียกว่า Bertrand's postulate ครับ เพราะว่าเคยเป็น conjecture ของ Bertrand มาก่อน มีเรื่องน่าสนใจอยู่อันนึง (หวังว่าคงมีคนสนใจบ้างล่ะน้า ) คือเมื่อ Erdos อายุ 18 ปี เขาได้แสดงความเป็นอัจฉริยะออกมาโดยการพิสูจน์ Bertrand's postulate ด้วยตนเอง ทำให้ Nathan J. Fine แต่งกลอนต่อไปนี้ขึ้นมาครับ

Chebychev said it, and I'll say it again,
There's always a prime between N and 2N.

[nooonuii]

เออ พูดถึงปู่ Erdos แล้วอยากถามคุณ Warut นิดนึงครับว่า คุณ Warut มีรหัส Erdos ใช่ป่ะครับ

[warut]

ไม่มีคร้าบ ผมเป็นแค่มือสมัครเล่น คือเป็นผู้ที่สนใจคณิตศาสตร์เฉยๆน่ะครับ จะว่าไปก็คล้ายๆอย่างคุณ gon นี่แหละ แต่อนาคตยังไม่แน่ครับ สักวันอาจจะได้มีโอกาสฝึกให้เป็นมือโปรแบบคุณ nooonuii คุณ Punk คุณ nongtum ฯลฯ ก็ได้ถ้าไม่ตาย หรือไปบวชซะก่อนนะครับ

ป.ล. ถ้าคุณ nooonuii มีรหัส Erdos อย่าลืมชวนผมไปเขียนอะไรด้วยนะครับ ผมจะได้ขอพ่วงไปด้วยคน (ไถอย่างไม่อายเลยนะเนี่ย )

[passer-by]

ข้อความเดิมของคุณ warut :
แต่ถ้าพิสูจน์ lemma นี้ได้แล้วที่เหลือก็จะตามมาทันทีเลยใช่มั้ยครับ

ใช่ครับ แล้วก็เหมือนที่คุณ warut อธิบายต่อจากข้อความข้างบนนี้ แหละครับ

ข้อความเดิมของคุณ warut :
อ๋อ เห็นแล้วครับ เป็น Problem 44 นั่นเอง เท่าที่ดูโจทย์ในนั้นมีแต่ยากๆทั้งนั้นเลย

ใช่ครับ ยากสุดๆไปเลย ผมเข้าใจว่า Professor คนนี้ น่าจะเป็นหนึ่งในคนที่ train นักศึกษาไปแข่ง William putnam competition หรือที่ผมเรียกเล่นๆว่า เป็นการแข่งเลขโอลิมปิกระดับอุดมศึกษา ดีๆนี่เอง

อ้อ! ผมอ่านบทพิสูจน์ของคุณ warut โดยละเอียดแล้วล่ะครับ รู้สึกดีกว่าตอนที่เห็นแวบแรก มากๆ

[nooonuii]

ข้อความเดิมของคุณ warut:
ไม่มีคร้าบ ผมเป็นแค่มือสมัครเล่น คือเป็นผู้ที่สนใจคณิตศาสตร์เฉยๆน่ะครับ จะว่าไปก็คล้ายๆอย่างคุณ gon นี่แหละ แต่อนาคตยังไม่แน่ครับ สักวันอาจจะได้มีโอกาสฝึกให้เป็นมือโปรแบบคุณ nooonuii คุณ Punk คุณ nongtum ฯลฯ ก็ได้ถ้าไม่ตาย หรือไปบวชซะก่อนนะครับ

ป.ล. ถ้าคุณ nooonuii มีรหัส Erdos อย่าลืมชวนผมไปเขียนอะไรด้วยนะครับ ผมจะได้ขอพ่วงไปด้วยคน (ไถอย่างไม่อายเลยนะเนี่ย )

โอยผมคงได้รหัสนี้มายากหน่อยครับเพราะผมไม่เก่งทฤษฎีจำนวนกับ combinatorics เอาซะเลย คงมีโอกาสร่วมงานกับคนที่ทำงานทางด้านนี้ได้ยากครับ ไอ้ผมก็คิดว่าคุณ Warut มีไงจะได้ขอแจมด้วยอิอิ แต่เอ่อเก่งๆอย่างคุณ Warut นี่ยังไม่โปรอีกเหรอครับ อ้อคุณ Warut เป็นนักล่าจำนวนเฉพาะด้วยหรือเปล่าครับ วันก่อนเข้าไปดูเวบพวกนี้เห็นเขาเล่นกันน่าสนุกจัง

[warut]

อืม ผมเป็นประเภทรู้บ้างไม่รู้บ้าง ขาดพื้นฐานหลายๆด้าน เพราะขาดการเริ่มต้นที่ถูกต้อง กว่าจะรู้ว่าถ้าสนใจคณิตศาสตร์สมัยนี้เราควรจะต้องรู้อะไรบ้างก็แก่มากแล้ว แต่คิดว่ายังพอจะแก้ไขได้ครับ และพยายามจะรีบทำด้วย เริ่มเมื่อไหร่คงมีคำถามมาถามในบอร์ดนี้บ่อยขึ้นแหละครับ (ถ้าพื้นฐานผมแน่นอย่างคุณ nooonuii ผมโม้แหลกไปนานแล้วครับ ไม่ต้องห่วง )

สำหรับเรื่องล่าจำนวนเฉพาะเคยทำเมื่อนานมาแล้วครับ แต่มีเหตุที่ทำให้ต้องชะงักไปช่วงนึง เลยไม่ได้กลับไปทำอีก เพราะติดตามความก้าวหน้าในด้านต่างๆไม่ทันเลยครับ

สำหรับเรื่อง Erdos number นี่ ผมว่าเลขรหัสสูงๆ คงไม่จำเป็นต้องเกี่ยวกับทฤษฎีจำนวนมั้งครับ ปัญหานอกจากเรื่องของความสามารถแล้วก็ยังมีเรื่องสีผิวอีก ผิวเหลือง (หรืออาจจะคล้ำๆหน่อย) อย่างเราคงยากครับ เพราะลึกๆพวกฝรั่งจำนวนไม่น้อยยังเหยียดผิวอยู่ แม้จะไม่แสดงออกอย่างโจ๋งครึ่มก็ตามที อันนี้พูดจากประสพการณ์ของผมเองนะครับ ถ้าใครไม่เจอหรือไม่รู้สึกก็นับเป็นโชคดีไป อย่างสมัยผมยังเล่นล่าจำนวนเฉพาะอยู่ เคยคิดเทคนิคใหม่ๆในการหาจำนวนเฉพาะไว้ 2-3 อย่าง ไม่ได้ลึกซึ้งอะไรหรอกครับ แต่อย่างน้อยก็ยังไม่เคยมีใครใช้ พอผมโพสต์เข้าไปใน mailing list สักพักก็มีคนเอาไปใช้กันเกร่อ ไม่มีใครเคยให้เครดิตผมสักคนเดียว เซ็งเลย ฝรั่งเข้มงวดกับเรื่องการให้เครดิตกับเฉพาะเครดิตที่ต้องให้กับพวกเค้า ถ้าเป็นพวกเราเค้าก็ไม่สน เกิดเป็นคนไทยเลยโชคร้ายสองต่อ คนไทยก็ไม่ค่อยให้เครดิตกันเอง (เราเพิ่งจะเริ่มให้ความสำคัญกับเรื่องนี้ได้ไม่นาน) แล้วฝรั่งก็ยังไม่เต็มใจให้เครดิตเราอีก (ถ้าไม่ใช่เรื่องใหญ่จริงๆ อย่างเรื่องที่มีคนอินเดียพิสูจน์เมื่อเร็วๆนี้ว่า การทดสอบความเป็นจำนวนเฉพาะเป็นปัญหาในกลุ่ม P ก็ไม่ค่อยให้เครดิตหรอกครับ แถมปฏิกิริยาของฝรั่งยังออกมาในลักษณะที่ว่าทำไมเค้า "overlook" เรื่องง่ายๆแค่นี้ไปได้ แหวะๆๆ)

[nooonuii]

อืม คุณ Warut มีประสบการณ์ที่ไม่ดีเกี่ยวกับเรื่องพวกนี้ด้วยหรือครับ เรื่องเหยียดสีผิวเนี่ยมันแก้ไม่หายหรอกครับ ผมมาอยู่ที่นี่ก็รู้สึกได้ดี
อ้าวไปๆมาๆยึดกระทู้คุณ passer-by กันซะแล้ว

[passer-by]

ข้อความเดิมของคุณ warut:
มีคนอินเดียพิสูจน์เมื่อเร็วๆนี้ว่า การทดสอบความเป็นจำนวนเฉพาะเป็นปัญหาในกลุ่ม P ก็ไม่ค่อยให้เครดิตหรอกครับ แถมปฏิกิริยาของฝรั่งยังออกมาในลักษณะที่ว่าทำไมเค้า "overlook" เรื่องง่ายๆแค่นี้ไปได้ แหวะๆๆ

ได้ข่าวเรื่อง Prime is in P เหมือนกันครับ แต่เรื่องปฏิกิริยาของฝรั่งนี้ ถือเป็นข่าวใหม่สำหรับผมเลยนะเนี่ย

ข้อความเดิมของคุณ nooonuii:
เรื่องเหยียดสีผิวเนี่ยมันแก้ไม่หายหรอกครับ ผมมาอยู่ที่นี่ก็รู้สึกได้ดี

ผมเคยได้ยินแต่ ฝั่งอังกฤษ discriminate คนเอเชียสุดๆ แต่ไม่ยักกะรู้ว่าฝั่งอเมริกา ก็หนักพอๆกัน ฟังแล้วเซ็งแทน

ข้อความเดิมของคุณ nooonuii:
อ้าวไปๆมาๆยึดกระทู้คุณ passer-by กันซะแล้ว

ไม่เป็นไรหรอกครับ ถือว่าเล่าสู่กันฟังเพลินๆ