Nilai daya polinomial
$f(x) = a_0 + a_1 x + a_2 x^2 + \dots + a_n x^n$ adalah polinomial derajat $n$ dengan koefisien bilangan bulat positif.
Pernyataan masalah utama: Apakah Persamaan Diophantine Eksponensial$f(f(a) + 1) = y^m$ solvable dalam bilangan bulat $y, m \geq 2, a$?
Latar belakang: Masalah ini muncul dalam pengkodean dan representasi data untuk kompresi. Diberikan$n + 1$ nilai data (pikirkan byte dengan nilai mulai 0 hingga 255), kami mewakili mereka sebagai koefisien integer $f(x)$. Kami membutuhkan nilai data untuk semua menjadi bilangan bulat positif$\ge 0$. Dalam kondisi ini,$f(1)$hanyalah jumlah dari koefisien. Membiarkan$b = f(1) + 1$ dan $c = f(b)$. Diberikan hanya nilai-nilai$c$ dan $b$, kami dapat memulihkan koefisien $a_0, a_1, \dots, a_n$ melalui pembagian berulang $c$ oleh $b$. yaitu, basis-$b$ perwakilan dari $c$ memiliki koefisien $f(x)$.
Basis ini-$b$ representasi dan pemulihan bekerja untuk semua pilihan $b$ yang lebih besar dari tinggi polinomial $f(x)$. $f(a) + 1$ dijamin lebih besar dari tinggi polinomial.
Pernyataan Masalah Alternatif: Apakah Persamaan Diophantine Eksponensial$f(b) = y^m$ memiliki solusi integer $b, y, m \geq 2$, dimana $b > \max(a_0, a_1, a_2, \dots, a_n)$.
Kompresi muncul dari fakta bahwa kami menggunakan kekuatan sempurna untuk menyandikan sekumpulan nilai. Harapannya adalah$b, y, m$ berukuran kecil dan membutuhkan lebih sedikit bit untuk diwakili daripada data asli.
Jawaban yang dapat diterima dapat menyelesaikan Pernyataan Masalah Utama atau Pernyataan Masalah Alternatif.
Editan:
- $GCD(a_0, a_1, \dots, a_n) = 1$ dapat dianggap sebagai suatu kondisi
Referensi:
Richmond, B. http://csclub.uwaterloo.ca/%7En3parikh/On%20a%20Perplexing%20Polynomial%20Puzzle.pdf.
Jawaban
Pertimbangkan kasus paling sederhana di mana $f(x)=a_0+a_1x$ dan $(a_0,a_1)=1$. Kemudian$$y^m=f(f(x)+1)=(a_0+a_1+a_0a_1)+a_1^2x$$ dan tulis $y=a_1^2n+k$ untuk beberapa bilangan bulat $k$ seperti yang $(a_1,k)=1$. Kami mendapatkan$$k^m\equiv a_0+a_1+a_0a_1\pmod{a_1^2}$$ dan memilih $m=2$ maksudnya $a_0+a_1+a_0a_1$ adalah residu kuadrat dari $a_1^2$. Artinya itu$$\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$$menggunakan notasi simbol Legendre. Kita dapat mengevaluasi istilah pertama sebagai berikut$$\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}$$ dengan mencatat itu $(a_1^2-a_1-2)^2/4\equiv a_1+1\pmod{a_1^2}$ kapan $a_1$ aneh.
Dalam kasus pertama, memilih $a_0=a_1^2-3a_1+1$ cukup untuk semua $a_1>3$ sebagai $a_0+a_1$ adalah kotak sempurna dan $(a_0,a_1)=1$. Ini cukup untuk menghasilkan bukan hanya satu, tetapi dua set solusi tak terbatas.
Untuk nilai ini $a_0$, kesesuaian $k^m\equiv a_0+a_1+a_0a_1\pmod{a_1^2}$ dikurangi menjadi $$k^2\equiv-a_1+1\pmod{a_1^2}\implies k=\frac{a_1^2\pm(a_1-2)}2$$ setelah menghapus istilah tingkat tinggi.
Seperti fungsi "pembangkit" $f(x)=r^2-3r+1+r^2x$ saat mengganti $r:=a_1$, menggantikan ini kembali menjadi $y^2=f(f(x)+1)$ menghasilkan dua keluarga $$(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)$$ untuk semua bilangan bulat positif $n$ dan aneh $r\ge5$.
Seseorang dapat memperoleh kumpulan solusi lebih lanjut dengan memilih $a_0=a_1^2-(2c+1)a_1+c^2$ untuk bilangan bulat positif $c>1$ dengan ketentuan $(a_0,a_1)=1$ lalu mengulangi proses di atas.
Saya telah menemukan polinomial tanpa solusi apa pun. Membiarkan$n=1$ dan
$$f(x)=2+4x$$
Kemudian
$$f(f(r)+1)=2(7+8r)=y^m$$
Ini menyiratkan $y$genap. Tapi kemudian$y=2k$ memberi
$$2^m k^m=2(7+8r)$$
$$2^{m-1}k^m=7+8r$$
Sisi kiri selalu genap (sejak $m\geq 2$) sedangkan sisi kanan selalu ganjil. Kami menyimpulkan tidak ada$y$ dan $m\geq 2$ yang memecahkan persamaan diophantine eksponensial.
Namun, masih banyak hal menarik yang mungkin bisa dilakukan untuk mengatasi masalah ini. Saya pikir itu secara umum, menambahkan syarat itu
$$\gcd(a_0,a_1,...,a_n)=1$$
mungkin berhasil menjamin solusi. Namun, saya belum membuktikannya. Misalnya, jenis masalah yang sama muncul saat Anda mempertimbangkan polinomial berikut
$$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$$