จำนวนกราแฮม

แม่แบบ:ต้องการอ้างอิง จำนวนกราแฮม (แม่แบบ:Langx) ตั้งชื่อตามชื่อของ โรนัลด์ กราแฮม เป็นจำนวนที่ได้รับการรับรองจากกินเนสส์บุ๊คว่าเป็นจำนวนที่มีค่ามากที่สุดเท่าที่เคยใช้ในบทพิสูจน์ทางคณิตศาสตร์

นิยามของจำนวนกราแฮม

จำนวนกราแฮม สามารถนิยามโดยใช้สัญลักษณ์ลูกศรของคนูธได้ว่า

$\begin{array}{ccc}G& =& 3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \uparrow }3\\ & & 3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow }3\\ & & \underbrace{⋮}\\ & & 3\underbrace{\uparrow \uparrow \cdots \cdot \cdot \uparrow }3\\ & & 3\uparrow \uparrow \uparrow \uparrow 3\end{array}\}\text{64 layers}$

โดยที่ ลูกศร ของแต่ละชั้น (layer) มีจำนวนเท่ากับค่าของชั้นที่อยู่ถัดลงมา เมื่อเริ่มต้นจากชั้นบนสุด (ชั้นที่ 64) สามารถอธิบายเป็นสูตรทางคณิตศาสตร์ได้ดังนี้

$G=g_{64},\text{ where }{g}_1=3\uparrow \uparrow \uparrow \uparrow 3,g_n=3{\uparrow }^{g_{n-1}}3,$

ปัญหาของกราแฮม

จำนวนกราแฮมมีที่มาจากปัญหาของกราแฮม ดังนี้

พิจารณาลูกบาศก์ n มิติ เชื่อมจุดยอดทุกคู่ให้เกิดกราฟสมบูรณ์ที่มีจุดยอด $2^n$ จุด จากนั้นระบายสีเส้นเชื่อมทุกเส้นด้วยสี 2 สี ค่าของ n ที่น้อยที่สุดเป็นเท่าไรที่จะต้องเกิดกราฟสมบูรณ์ที่มีจุดยอด 4 จุดซึ่งอยู่บนระนาบเดียวกันและทุกเส้นเชื่อมมีสีเดียวกัน

อย่างไรก็ตาม ยังไม่มีใครค้นพบคำตอบของปัญหาข้อนี้ ในปี 1971 กราแฮมกับรอธส์ไชลด์ ได้พิสูจน์ว่าคำตอบของปัญหา N* จะต้องเป็นไปตาม 6 ≤ N* ≤ N เมื่อ N เป็นจำนวนค่ามากที่เท่ากับ $F^7(12)=F(F(F(F(F(F(F(12)))))))$ เมื่อ $F(n)=2{\uparrow }^{n}3$ ตามสัญกรณ์ลูกศรของคนูธ หากใช้สัญกรณ์ลูกศรขวาของคอนเวย์ N มีค่าระหว่าง 4 → 2 → 8 → 2 กับ 2 → 3 → 9 → 2 ต่อมาในปี 2014 ขอบเขตบนถูกลดลงเหลือ $N^{\prime }=2\uparrow \uparrow \uparrow 6$ ส่วนขอบเขตล่างเพิ่มเป็น 11 ในปี 2003 และ 13 ในปี 2008

สำหรับจำนวนกราแฮม G เป็นขอบเขตบนที่มีค่ามากยิ่งกว่า N ถูกค้นพบโดยกราแฮม และต่อมาได้ตีพิมพ์โดยมาร์ติน การ์ดเนอร์ ใน Scientific American ทำให้เป็นที่รู้จักมากกว่า แม่แบบ:โครงคณิตศาสตร์