बहुपद के शक्ति मान
$f(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_n x^n$ डिग्री का बहुपद है $n$ सकारात्मक पूर्णांक गुणांक के साथ।
प्राथमिक समस्या बयान: एक्सपोनेंशियल डायोफैंटाइन समीकरण है$f(f(a) + 1) = y^m$ पूर्णांक में विलेय $y, m \geq 2, a$?
पृष्ठभूमि: यह समस्या संपीड़न के लिए डेटा एन्कोडिंग और प्रतिनिधित्व में उत्पन्न होती है। दिया हुआ$n + 1$ डेटा मान (0 से 255 तक के मानों के साथ बाइट्स), हम उन्हें पूर्णांक गुणांक के रूप में दर्शाते हैं $f(x)$। हमें सभी डेटा पूर्णांक सकारात्मक होने चाहिए$\ge 0$। इस शर्त के तहत,$f(1)$सिर्फ गुणांकों का योग है। चलो$b = f(1) + 1$ तथा $c = f(b)$। सिर्फ मूल्यों को देखते हुए$c$ तथा $b$, हम गुणांक को पुनर्प्राप्त कर सकते हैं $a_0, a_1, \dots, a_n$ के बार-बार विभाजन के माध्यम से $c$ द्वारा $b$। आधार, आधार-$b$ का प्रतिनिधित्व $c$ के गुणांक है $f(x)$।
यह आधार-$b$ प्रतिनिधित्व और पुनर्प्राप्ति किसी भी विकल्प के लिए काम करता है $b$ यह बहुपद की ऊंचाई से अधिक है $f(x)$। $f(a) + 1$ बहुपद की ऊंचाई से अधिक होने की गारंटी है।
वैकल्पिक समस्या विवरण: क्या घातीय डायोफैंटाइन समीकरण है$f(b) = y^m$ पूर्णांक समाधान है $b, y, m \geq 2$, कहाँ पे $b > \max(a_0, a_1, a_2, \dots, a_n)$।
संपीड़न इस तथ्य से उत्पन्न होता है कि हम मूल्यों के एक सेट को एन्कोड करने के लिए सही शक्तियों का उपयोग कर रहे हैं। उम्मीद है$b, y, m$ छोटे हैं और मूल डेटा की तुलना में कम बिट्स की आवश्यकता होती है।
स्वीकार्य उत्तर प्राथमिक समस्या कथन या वैकल्पिक समस्या कथन को हल कर सकता है।
संपादन:
- $GCD(a_0, a_1, \dots, a_n) = 1$ एक शर्त के रूप में माना जा सकता है
संदर्भ:
रिचमंड, बी। http://csclub.uwaterloo.ca/%7En3parikh/On%20a%20Perplexing%20Polynomial%20Puzzle.pdf।
जवाब
सबसे सरल मामले पर विचार करें जहां $f(x)=a_0+a_1x$ तथा $(a_0,a_1)=1$। फिर$$y^m=f(f(x)+1)=(a_0+a_1+a_0a_1)+a_1^2x$$ और लिखा $y=a_1^2n+k$ कुछ पूर्णांक के लिए $k$ ऐसा है कि $(a_1,k)=1$। हमने प्राप्त किया$$k^m\equiv a_0+a_1+a_0a_1\pmod{a_1^2}$$ और चुनना $m=2$ मतलब कि $a_0+a_1+a_0a_1$ का एक द्विघात अवशेष है $a_1^2$। इस का मतलब है कि$$\left(\frac{a_0+a_1+a_0a_1}{a_1^2}\right)=\left(\frac{a_1+1}{a_1^2}\right)\left(\frac{a_0+a_1}{a_1^2}\right)=1$$लीजेंड्रे प्रतीक अंकन का उपयोग करना। हम पहले शब्द का मूल्यांकन इस प्रकार कर सकते हैं$$\left(\frac{a_1+1}{a_1^2}\right)=\begin{align}\begin{cases}1&\text{if}\,a_1\,\text{is odd or}\, \sqrt{a_1+1}\,\text{is an integer}\\-1&\text{otherwise}\end{cases}\end{align}$$ यह देखते हुए $(a_1^2-a_1-2)^2/4\equiv a_1+1\pmod{a_1^2}$ कब $a_1$ अजीब है।
पहले मामले में, चुनना $a_0=a_1^2-3a_1+1$ सभी के लिए पर्याप्त है $a_1>3$ जैसा $a_0+a_1$ एक आदर्श वर्ग है और $(a_0,a_1)=1$। यह एक नहीं, बल्कि दो अनंत समाधानों को उत्पन्न करने के लिए पर्याप्त है।
के इस मूल्य के लिए $a_0$, बधाई हो $k^m\equiv a_0+a_1+a_0a_1\pmod{a_1^2}$ को कम करता है $$k^2\equiv-a_1+1\pmod{a_1^2}\implies k=\frac{a_1^2\pm(a_1-2)}2$$ उच्च-आदेश की शर्तों को हटाने के बाद।
जैसा कि "जनरेटिंग" फंक्शन है $f(x)=r^2-3r+1+r^2x$ बदलने पर $r:=a_1$, इस में वापस प्रतिस्थापित $y^2=f(f(x)+1)$ दोनों परिवारों को पैदावार देता है $$(x,y)=\left(r^2n^2+(r^2\pm(r-2))n+\frac{(r-1)^2}2\pm(r-2),r^2n+\frac{r^2\pm(r-2)}2\right)$$ सभी सकारात्मक पूर्णांकों के लिए $n$ और विषम $r\ge5$।
एक चुनकर आगे समाधान सेट प्राप्त कर सकते हैं $a_0=a_1^2-(2c+1)a_1+c^2$ एक सकारात्मक पूर्णांक के लिए $c>1$ उसे उपलब्ध कराया $(a_0,a_1)=1$ और फिर ऊपर की प्रक्रिया को दोहरा रहा है।
मैंने बिना किसी समाधान के एक बहुपद पाया है। चलो$n=1$ तथा
$$f(x)=2+4x$$
फिर
$$f(f(r)+1)=2(7+8r)=y^m$$
इसका अर्थ है $y$सम है। परन्तु फिर$y=2k$ देता है
$$2^m k^m=2(7+8r)$$
$$2^{m-1}k^m=7+8r$$
बाईं ओर भी हमेशा से है (तब से $m\geq 2$) जबकि दाईं ओर हमेशा विषम है। हम निष्कर्ष निकालते हैं कि कोई नहीं है$y$ तथा $m\geq 2$ जो घातीय डायोफैंटाइन समीकरण को हल करता है।
हालांकि, अभी भी बहुत सारी दिलचस्प चीजें हैं जो इस समस्या के साथ हो सकती हैं। मुझे लगता है कि सामान्य तौर पर, इस शर्त को जोड़ना है कि
$$\gcd(a_0,a_1,...,a_n)=1$$
एक समाधान की गारंटी देने में सफल हो सकता है। हालांकि, मैंने यह साबित नहीं किया है। उदाहरण के लिए, जब आप निम्नलिखित बहुपद पर विचार करते हैं तो उसी तरह की समस्या उत्पन्न होती है
$$f(x)=2+2x+2x^2$$
$$f(x)=2+2x+2x^2+4x^3$$
$$f(x)=2+2x+2x^2+2x^3+2x^4$$
$$\vdots$$