# A Non-NP-Complete Algorithm for a Quasi-Fixed Polynomial Problem

Authors: Yi-Chou Chen; Hang-Chin Lai
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

LetF:ℝ×ℝ→ℝ be a real-valued polynomial function of the form F(x,y)=∑i=0s‍fi(x)yi, with degree of y in F(x,y)=s≥1,x∈ℝ. An irreducible real-valued polynomial function p(x) and a nonnegative integer m are given to find a polynomial function y(x)∈ℝ[x] satisfying the following expression: F(x,y(x))=cpm(x) for some constant c∈ℝ. The constant c is dependent on the solution y(x), namely, a quasi-fixed (polynomial) solution of the polynomial-like equation (*). In this paper, we will provide a non-NP-complete algorithm to solve all quasi-fixed solutions if the equation (*) has only a finite number of quasi-fixed solutions.


---

## Body

## 1. Introduction and Preliminaries

Lenstra [1] found that a polynomial function F(x,y)∈ℚ(α)[x,y](where α is an algebraic number) can be solved to a polynomial function y=y(x)∈ℚ(α)[x] such that F(x,y(x))=0. It can thus be derived to find a polynomial y=y(x) such that there exists an x∈ℚ(α)[x] as a fixed point of the polynomial function F(x,y(x)); that is,
(1)F(x,y(x))=x
has a polynomial solution y(x)∈ℚ(α)[x].Furthermore, Tung [2, 3] extended (1) to solve y(x) for the following equation:
(2)F(x,y(x))=cxm,forx∈𝕂(field),m∈ℕ,
where c is a real constant depending on the polynomial solution y(x) and the given positive integer m∈ℕ.Recently, Lai and Chen [4] extended the expression (2) to solve y(x) to satisfy the polynomial equation as the following form:
(3)F(x,y(x))=cpm(x),x∈ℝ,
where p(·) is an irreducible polynomial in x∈ℝ and the polynomial functions F(x,y):ℝ×ℝ→ℝ are written by
(4)F(x,y)=∑i=0s‍fi(x)yi,with  degreeyinF(x,y)denoted  bydegyF=s>1.Remark 1.
Recall that a polynomial functiony=y(x) satisfying (3) is called a quasi-fixed (polynomial) solution corresponding to the real value a. This number a is called a quasi-fixed (polynomial) value corresponding to the polynomial solutions y=y(x).
Note that the equation may not be solvable; if it is solvable, the number of all solutions may be infinitely many, or finitely many quasi-fixed solutions If this equation has infinitely many quasi-fixed solutions, by [4, Theorem 3.5], we have(1)
fs(x) must be apr(x) for some a∈ℝ, r∈ℕ,(2)
those solutions must assume a fixed form like(5)-fs-1(x)sfs(x)+λpk(x)for  anyλ∈ℝ.
Moreover, if this equation has only finitely many quasi-fixed solutions, by [4, Corollary 3.3], the bound of all solutions is at most degyF+2.In this paper, we deal with the case of finitely many solutions and provide a non-NP-complete algorithm to obtain all representations of quasi-fixed solutions.Remark 2.
An algorithm is called “NP-complete” if the algorithm is computed in an exponential time of the input size “n”; that is, the computing time in the algorithm does not exceed O(en). Otherwise, the algorithm is called “non-NP-complete”; that is, the algorithm can be computed in a polynomial time not exceeding O(nk) for some fixed real number k.The remainder of the paper is organized as follows: Section2 introduces an example for the practical algorithm. Section 3 describes the main algorithm and its processes. Section 4 proves that the main algorithm is indeed non-NP-complete. We have given two example problems in Section 5.


## 2. Relative Algorithm and Some Examples

LetF(x,y)∈ℝ[x,y] and an irreducible polynomial function p(x)∈ℝ[x]. To complete our algorithm, we need an existing algorithm. In [2], Tung has established the following algorithm.Algorithm 3 (Tung [5]).
Consider the following technique.
Input. Given is a polynomial F(x,y)∈ℝ[x,y].
Output. All solutions y=y(x) satisfy
(6)F(x,y(x))=a,for  somea∈ℝ,
in polynomial time of wμ, where w is the computer memory of all coefficients of F(x,y) and μ=degxF(x,y)+degyF(x,y). Moreover, the number of all solutions is at most degyF(x,y).We provide a simple example to explain our aim for solving the quasi-fixed polynomial solutions related to Algorithm5 (in Section 3) as follows.Example 4.
Let(7)F(x,y)=p(x)[y2-p2(x)-4]
and p(x)=x2+x+1. Then degyF=s=2. Solve all quasi-fixed solutions of
(8)F(x,y)=ap2(x).
By (7) and (8), we obtain
(9)p(x)[y2-p2(x)-4]=ap2(x),
divides both sides by p(x), then it becomes
(10)y2-p2(x)-4=ap(x).
It follows that(11)y2-4=0modp(x),
and we have
(12)y={zp(x)+2zp(x)-2={2(modp(x))-2(modp(x)),
with an indeterminate z. To determine z, we substitute this y (in (12)) into F(x,y), then (8) becomes
(13)(P1){(1)F(x,y)=F(x,zp(x)+2)=ap2(x)(2)F(x,y)=F(x,zp(x)-2)=ap2(x).
This yields(14)(P2){(1)p2(x)[p(x)z2+4z-p(x)]=ap2(x)(2)p2(x)[p(x)z2-4z-p(x)]=ap2(x).
Both sides of (14) divide by p2(x) to become
(15)(P3){(1)p(x)z2+4z-p(x)=a(2)p(x)z2-4z-p(x)=a.
According to Algorithm3, we obtain z=1 and z=-1, so the solutions (12) of problem (P) are
(16)y={zp(x)+2zp(x)-2={p(x)+2p(x)-2or{-p(x)+2-p(x)-2.In Section3, we provide a non-NP-complete algorithm to satisfy (3).


## 3. Computing Procedure

In this paper, we may assume that the number of all solutions of (3) is finite and then constitute an algorithm of the approximate solutions for the quasi-fixed polynomial equation (3) as follows.Algorithm 5.
Consider the following technique.
Input. Given a polynomial F(x,y)∈ℝ[x,y], p(x)∈ℝ[x] irreducible and m∈ℕ.
Output. All solutions y=y(x) satisfy
(17)F(x,y(x))=apm(x)for  somea∈ℝ,
by a non-NP-complete algorithm.The following definitions are given by [6, page 421].Definition 6.
(i) The content ofF(x,y) in (4), denoted by contyF, is defined by the greatest common divisor (g.c.d):
(18)gcd(fs(x),fs-1(x),…,f0(x))=contyF.
(ii) The primitive partppyF of F(x,y) is F(x,y)/contyF∈ℝ[x,y], and F(x,y) is primitive if contyF=1.
From (i) and (ii), we have(19)F(x,y)=contyF·ppyF.To complete the following algorithm, we need the following elementary property.Lemma 7.
LetF(x,y)∈ℝ[x,y] and p(x) be an irreducible polynomial in ℝ[x]. Consider the module equation
(20)F(x,y)=0(modp(x)).
The number of all solutionsy=y(x)(modp(x)) is thus at most degyF.Assumption. Throughout this algorithm, for any F(x,y)∈ℝ[x,y], one can solve all solutions y=g(x)(modp(x)) of the equation
(21)F(x,g(x))=0modp(x).The procedure of our main algorithm is described below.Procedures of Main Algorithm (Algorithm5)Step  0. If contyF∣pm(x) and contyF=1, then let F1(x,y)=F(x,y) and move to (Step 1, (1.2.2)).Step  1. For convenience, we let
(22)F(x,y)=(contyF)F1(x,y),
where F1(x,y)∈ℝ[x,y] is a primitive polynomial.Step  1.1. If contyF∤pm(x), we would have the problem
(23)F(x,y)=cpm(x),
to deduce that contyF∣c·pm(x). But contyF∤pm(x), then c=0. Consequently, (23) becomes
(24)F(x,y)=0.We can then solve all solutionsy(x) for F(x,y)=0 to get a solution set
(25)Y0={y(x):F(x,y(x))=0}.Step  1.2. If contyF∣pm(x) and contyF≠1, then contyF=pℓ1(x) with ℓ1≤m. In this case, (23) becomes
(26)F1(x,y)=cpm-ℓ1(x).Step  1.2.1. In case ℓ1=m, then (26) becomes F1(x,y)=c which can be solved by Algorithm 3 to obtain all solutions for the equation F1(x,y)=c to get y=y(x) and obtain a set
(27)W0={y(x):F1(x,y(x))=c}.Step  1.2.2. If ℓ1<m, then m-ℓ1>0 and we can divide both sides of (26) by p(x); consequently,
(28)F1(x,y)=0(modp(x)).According to Lemma7, the solution number does not exceed degyF, thus we may assume that y=a0(x) is a solution of (28) with dega0(x)<degp(x); please note that the choice of a0(x) may be larger than 1 and we may define a solution set T0(F) which collects such a0(x) by setting as the following form:
(29)a0(x)∈T0(F)={a10(x),a20(x),…,ar00(x)}.Consequently, the expression (23) can go to Step 2.Step  2. For each a0(x)∈T0(F) in (Step 1, (1.2.2)), we can replace y by zp(x)+a0(x) in (23), and then (23) becomes
(30)F(x,zp(x)+a0(x))=cpm(x).We letH1(x,z)=F(x,zp(x)+a0(x)). Thus it follows from Definition 6(ii) that there exists
(31)F2(x,y)=ppyH1∈ℝ[x,y]
which is a primitive polynomial function so that
(32)H1(x,y)=(contyH1)F2(x,y).Equation (30) then becomes
(33)H1(x,y)=cpm(x).Next, we will prove thatp(x)∣contyH1.Step  2.1. If contyH1∤pm(x), (32) and (33) can be extrapolated as to contyH1∣c·pm(x). Since contyH1∤pm(x), then c=0. Consequently, (33) becomes
(34)H1(x,y)=0.We can then solve all solutionsy(x) for H1(x,y)=0 to get a solution set
(35)Y1={a0(x):H1(x,y(x))=0,a0(x)∈T0(F)y(x)p(x)+a0(x):H1(x,y(x))=0,a0(x)∈T0(F)}.Step  2.2. If contyH1∣pm(x), then contyH1=pℓ2(x) with ℓ2≤m. In this case, (33) becomes
(36)F2(x,y)=cpm-ℓ2(x).Step  2.2.1. In case ℓ2=m, (36) becomes
(37)F2(x,y)=c
which can be solved by Algorithm 3 to get y=y(x) and obtain a set
(38)W1={y(x)p(x)+a0(x):F2(x,y(x))=c,a0(x)∈T0(F)}.Step  2.2.2. If ℓ2<m, then m-ℓ2<0 and we can divide both sides of (36) by p(x); consequently,
(39)F2(x,y)=0(modp(x)).By the same reasoning used in [Step1.2.2], we can solve y=a1(x) with dega1(x)<degp(x) and obtain the set
(40)a1(x)∈V1={a11(x),a21(x),…,ar11(x)}.We let(41)T1(F)={a1(x)p(x)+a0(x):a1(x)∈V1,a0(x)∈T0(F)},Consequently, expression (33) can go to Step 3.Step  3. For each a1(x)p(x)+a0(x)∈T1(F), we can replace y by zp2(x)+a1(x)p(x)+a0(x) in (23). It then becomes
(42)F(x,zp2(x)+a1(x)p(x)+a0(x))=cpm(x).Moreover, we letH2(x,z)=F(x,zp2(x)+a1(x)p(x)+a0(x)) and
(43)H2(x,y)=(contyH2)F3(x,y)
for a primitive polynomial F3(x,y)=ppyH2∈ℝ[x,y], so that (42) becomes
(44)H2(x,y)=cpm(x).Next, we will prove thatp2(x)∣contyH2.Step  3.1. If contyH2∤pm(x), and (43) and (44) are extrapolated, we have
(45)contyH2∣c·pm(x).SincecontyH2∤pm(x), we have c=0.Thus (44) becomes
(46)H2(x,y)=0.Hence, we solve all solutionsy(x) such that H2(x,y)=0 to obtain a solution set
(47)Y2={y(x)p2(x)+a1(x)p(x)+a0(x):H2(x,y(x))=0,a1(x)p(x)+a0(x)∈T1(F)y(x)p2(x)+a1(x)p(x)+a0(x):H2(x,y(x))}.Step  3.2. If contyH2∣pm(x), then contyH2=pℓ3(x) for some positive integer ℓ3≤m and (44) becomes
(48)F3(x,y)=cpm-ℓ3(x).Step  3.2.1. If ℓ3=m, then (48) becomes
(49)F3(x,y)=c
and, by Algorithm 3, we compute y=y(x) and collect
(50)y(x)p2(x)+a1(x)p(x)+a0(x)
in W2 for all a1(x)p(x)+a0(x)∈T1(F). Hence, we output
(51)W2={y(x)p2(x)+a1(x)p(x)+a0(x):F3(x,y(x))=c,a1(x)p(x)+a0(x)∈T1(F)F3(xp2,y(x))}.Step  3.2.2. If ℓ3<m, we use p(x) to divide both sides of (48) to obtain
(52)F3(x,y)=0(modp(x)).By the same reasoning used in (Step1.2.2), we can solve y=a2(x) with dega2(x)<degp(x) and obtain the set
(53)a2(x)∈V2={a12(x),a22(x),…,ar22(x)}.We let(54)T2(F)={a2(x)p2(x)+a1(x)p(x)+a0(x)2:a2(x)∈V2,a1(x)p(x)+a0(x)∈T1(F){a2(x)p2(x)+a1(x)p(x)+a0(x)},
thus expression (44) can go to Step 4.Continuing this process, we get the(k-1)-th step and a sequence {ℓ1,ℓ2,…,ℓk-1} and go to the nextk-th step.Step
k
. For each ∑i=0k-2‍ai(x)pi(x)∈Tk-2(F), we can replace y by zpk-1(x)+⋯+a0(x) in (23), and then (23) becomes
(55)F(x,zpk-1(x)+⋯+a0(x))=cpm(x).We letHk-1(x,z)=F(x,zpk-1(x)+⋯+a0(x)) and
(56)Hk-1(x,y)=(contyHk-1)Fk(x,y)
for a primitive polynomial Fk(x,y)∈ℝ[x,y], then (55) becomes
(57)Hk-1(x,y)=cpm(x).Note that in Section4, Lemma 9, we will prove that pk-1(x)∣contyHk-1.Step  k.1. If contyHk-1∤pm(x), by (56) and (57), we have
(58)contyHk-1∣c·pm(x),
since contyHk-1∤pm(x), we have c=0.Thus (57) becomes
(59)Hk-1(x,y)=0.Hence, we solve all solutionsy(x) such that Hk-1(x,y)=0 to obtain a solution set
(60)Yk-1={y(x)pk-1+∑i=0k-2‍ai(x)pi(x):Hk-1(x,y(x))=0,∑i=0k-2‍ai(x)pi(x)∈Tk-2(F)}.Step  k.2. If contyHk-1∣pm(x), then contyHk-1=pℓk(x) for some positive integer ℓk≤m and (57) becomes
(61)Fk(x,y)=cpm-ℓk(x).Step  k.2.1. If ℓk=m, then (61) becomes
(62)Fk(x,y)=c.By Algorithm3, we compute y=y(x) and obtain
(63)y(x)pk-1(x)+ak-2(x)pk-2(x)+⋯+a0(x)
in Wk-1, for all ak-2(x)pk-2(x)+⋯+a0(x)∈Tk-2(F). Hence, we output
(64)Wk-1={∑i=0k-2‍y(x)pk-1(x)+⋯+a0(x):Fk(x,y(x))=c,∑i=0k-2‍ai(x)pi(x)∈Tk-2(F)}.Step  k.2.2. If ℓk<m, we use p(x) to divide both sides of (61) to obtain
(65)Fk(x,y)=0(modp(x)).By the same reasoning used in (Step1.2.2), we can solve y=ak-1(x) with degak-1(x)<degp(x) and obtain the set
(66)ak-1(x)∈Vk-1={a1k-1(x),a2k-1(x),…,ark-1k-1(x)}.We let(67)Tk-1(F)={∑i=0k-2‍ai(x)pi(x):ak-1(x)∈Vk-1,∑i=0k-2‍ai(x)pi(x)∈Tk-2(F)},
thus expression (57) can go to the next step.As explained in Remark8, this algorithm is not an infinite loop.Remark 8.
(i) IfVi=∅, then Vi+1=∅ and if Vi+1=∅, then Ti+1(F)=∅ for i≥0. This means that if Vi=∅, then the work finishes at step i+1for i≥0.
(ii) This algorithm is not an infinite loop. Sinceℓk<m, and by Corollary 13, we have ℓk<ℓk+1 for k=1,2,…, thus this algorithm will terminate at the(m+1)-th Step. We can thus say that this algorithm is a finite loop algorithm.
(iii) We may assume that the cardinal number|Wi|<∞, for i=1,2,…; however, if |Wi|=∞, then Algorithm 5 has an infinite number of solutions, which contradicts our assumption.Remark8(ii) shows that the maximum number of steps in this algorithm is m+1. Moreover, if the(m+1)-th Step happens, then we obtain
(68)pm(x)∣Hm(x,y)
by Corollary 11 and let
(69)Hm(x,y)=pm(x)Fm+1(x,y).Thus, the possible solutions ofHm(x,y)=cpm(x) are those solutions y(x) satisfying
(70)Fm+1(x,y(x))=c.Moreover, by Algorithm3, we can get a solution set Y such that the bound of all solutions is “s·|Tm-1(F)|.” So the solution set of (3) is contained in
(71)T=(⋃i=0m-1Yi)⋃‍(⋃i=0m-1Wi)⋃‍Y.Finally, we check each elementu(x)∈T to determine whether or not
(72)F(x,u(x))=cpm(x).The arithmetic computing time to solve each elementu(x) in T only requires non-NP-complete computing time and to check that each u(x)∈T satisfies
(73)F(x,u(x))=cpm(x).Non-NP-complete computing time is also needed given the cardinal number ofT:
(74)|T|≤|W0|+|Y0|+|Y|+∑i=0m-2|Wi+1|+∑i=0m-2‍|Yi+1|(ByAlgorithm3andLemma7)≤2s+s·|Tm-1(F)|+2∑i=0m-2‍s·|Ti(F)|,
where |Ti(F)|, |Wi|, and |Yi| denote the cardinal number of Ti(F), Wi, and Yi. The remaining work “Checks the bound of |Ti(F)|, for each i=1,2,…,m.” In Section 4, Theorem 16, we prove that
(75)|Ti(F)|≤s
for i=1,2,…,m-1.By (74) and (75), we have the cardinal number
(76)|T|≤2s+s·|Tm-1(F)|+2∑i=0m-2‍s·|Ti(F)|≤2s+s2+2∑i=0m-2‍s2=2s+(2m-1)s2.That is, we have to check at most “2s+(2m-1)s2” solutions u(x) to satisfy
(77)F(x,u(x))=cpm(x).Checking each solution only takes non-NP-complete time, thus this algorithm needs non-NP-complete time. That is, Algorithm 5 is indeed a non-NP-complete time algorithm. Note that, for eachk-th Step, whether y(x)pk-1(x)+ak-2pk-2(x)+⋯+a0(x) belongs to Yk-1 or Wk-1, the upper bound of all elements in T may not be as large; in fact,
(78)|T|≤2s+s2+(m-1)s2=2s+ms2.In the next Section4, we will complete all necessary properties for this algorithm.


## 4. Main Theorems

For convenience, we describe some interesting properties of the above algorithm.Lemma 9.
LetF(x,y)∈ℝ[x,y], p(x), a(x)∈ℝ[x], and z be a parameter, if p(x)∣F(x,a(x)), then p(x)∣F(x,zp(x)+a(x)).Proof.
LetF(x,y)=fs(x)ys+fs-1(x)ys-1+⋯+f0(x). Then
(79)F(x,zp(x)+a(x))=fs(x)(zp(x)+a(x))s+fs-1(x)(zp(x)+a(x))s-1+⋯+f0(x)=fs(x)(zsps(x)+szs-1ps-1a(x)+⋯+as(x))+fs-1(x)(zs-1ps-1(x)+(s-1)zs-2ps-2a(x)+⋯+as-1(x))+⋯+f0(x)=fs(x)(Qs(x,z)p(x)+as(x))+fs-1(x)×(Qs-1(x,z)p(x)+as-1(x))+⋯+f0(x)(whereQi(x,z)=zipi-1(x)+izi-1pi-2(x)a(x)+⋯+izai-1(x))=p(x)(fs(x)Qs(x,z)+fs-1(x)Qs-1(x,z)+⋯+f1(x)Q1(x,z))+(fs(x)as(x)+fs-1(x)as-1(x)+⋯+f0(x))=p(x)(fs(x)Qs(x,z)+fs-1(x)Qs-1(x,z)+⋯+f1(x)Q1(x,z))+F(x,a(x)).
Thus,p(x)∣F(x,a(x))⇒p(x)∣F(x,zp(x)+a(x)).The definitions ofHi(x,y), contyHi, Fi+1(x,y), and ai(x) for i=1,2,…,m+1 in Algorithm 5 are
(80)Hk(x,z)=F(x,zpk(x)+⋯+a0(x)),(81)Hk(x,y)=(contyHk)Fk+1(x,y),
for a primitive polynomial Fk+1(x,y)∈ℝ[x,y] and p(x)∣Fk+1(x,ak(x)) for k=0,1,…,m.Next, we prove some properties aboutHk(x,y) for k=1,2,…,m+1.Lemma 10.
Considerp(x)contyHk∣contyHk+1, for 1≤k≤m.Proof.
From (80), we have
(82)Hk+1(x,z)=F(x,zpk+1(x)+ak(x)pk(x)+⋯+a0(x))=F(x,(zp(x)+ak(x))pk(x)+⋯+a0(x))=Hk(x,zp(x)+ak(x))(by(80))=(contzHk)Fk+1(x,zp(x)+ak(x))(by(81)).
By definition ofak(x), we have p(x)∣Fk+1(x,ak(x)). From Lemma 9, we obtain p(x)∣Fk+1(x,zp(x)+ak(x)). That is,
(83)p(x)contyHk∣Hk+1(x,z),
and, by (81), we obtain p(x)contyHk∣contyHk+1.By Lemma9, p(x)∣H1(x,z), and the definition of contyH1, it follows that p(x)∣contyH1. Moreover, by Lemma 10, we can easily obtain the following corollaries.Corollary 11.
Considerpi(x)∣contyHi, for i≥1.To complete the main theorem, we give the following definitions.Definition 12.
(i) The functionf(x) is said to have p(x)-power ℓ, denoted by δp(f(x))=ℓ, if p(x)ℓ∣f(x) and p(x)ℓ+1∤f(x).
(ii) We say thatF(x,y) has p(x)-power ℓ, if contyF has p(x)-power ℓ.The following corollary is an immediate result of Lemma10 and Definition 12.Corollary 13.
Considerℓi<ℓi+1, for i≥1.Proof .
Sinceδp(Hi)=ℓi+1 and by Lemma 10, we have
(84)p(x)contyHk∣contyHk+1.
It follows that(85)1+δp(Hi)=δp(p(x)Hi)≤δp(Hi+1),
so 1+ℓi≤ℓi+1; hence, ℓi<ℓi+1.Next, we obtain some properties ofp(x)-power as follows.Lemma 14.
Letf(x), g(x), h(x)∈ℝ[x] and F(x,y) is defined in (4). Then (i)
δp(fg)=δp(f)+δp(g),(ii)
δp(f+g)≥min{δp(f),δp(g)}, and(iii)
δp(F)=min0≤i≤s{δp(fi)},(iv)
Ifh=f+g and δp(h)<δp(g), then δp(h)=δp(f).For eachk∈ℕ, we rewrite Tk(F) defined in the procedures of Algorithm 5 as the following definitions.Definition 15.
LetF(x,y)∈ℝ[x,y], an irreducible polynomial p(x)∈ℝ[x], and z be a parameter. We denote the sets Ti(F), i∈ℕ defined in Algorithm 5 as follows: (1)
T0(F)={a(x)∈ℝ[x]:p(x)contzF(x,z)∣F(x,a(x)) with 0≤dega(x)<degp(x)},(2)
Tk(F)={bk(x)∈ℝ[x]:bk(x)=a(x)pk(x)+bk-1(x) satisfies (D1) and (D2)} where for k≥1, and the (D1) and (D2) properties are given by the following:
(D1):
0≤dega(x)<degp(x) and bk-1(x)∈Tk-1(F),(D2):
p(x)contzF(x,zpk(x)+b(x))∣F(x,a(x)pk(x)+b(x)).From the above definitions, we obtain a bound of the cardinal number|Tk(F)|.Theorem 16.
For eachk∈ℕ, then |Tk(F)|≤degyF (|·| means the cardinal number).Proof .
This theorem will be proven by induction ondegyF.
(i) WhendegyF=1, claim that |Tk(F)|≤1 for any k∈ℕ.
For this purpose, we consider(86)F(x,y)=f1(x)y+f0(x)for  somef1(x),f0(x)∈ℝ[x].
(
1
) If k=0, and let v0=δp(F(x,z)) and F(x,y)=f1(x)y+f0(x)=pv0(x)(g10(x)y+g00(x)) for some coprime polynomials g10(x), g00(x)∈ℝ[x].
The only possible solutiona0(x) with 0≤dega0(x)<degp(x) and p(x)contyF(x,z)∣F(x,a0(x)) is
(87)a0(x)=(g10(x))-1(g00(x))modp(x).
That is,|T0(F)|≤1.
(
2
) Next, we assume that |Tk-1(F)|≤1, thus we deduce that |Tk(F)|≤1.
Let(88)vk=δp(F(x,zpk(x)+bk-1(x)))forsomebk-1(x)∈Tk-1(F),
and F(x,zpk(x)+bk-1(x))=pvk(x)(g1k(x)z+g0k(x)) for some g1k(x), g0k(x)∈ℝ[x]. Consider
(89)Tk(F)={bk(x)∈ℝ[x]:bk(x)=a(x)pk(x)+bk-1(x)satisfies(D1)and(D2)pk},
and since |Tk-1(F)|≤1 by assumption, bk-1(x) is uniquely decided, as is vk. The remaining task is to prove that ak is also uniquely determined. As bk(x)∈Tk(F) with bk(x)=ak(x)pk(x)+bk-1(x), ak(x) satisfies
(90)0≤degak(x)<degp(x)
such that
(91)p(x)contyF(x,zpk(x)+bk-1(x))∣F(x,ak(x)pk(x)+bk-1(x))forsomebk-1(x)∈Tk-1(F),
then
(92)ak(x)g1k(x)+g0k(x)=0modp(x),
it follows that ak(x) must be
(93)ak(x)=(g1k(x))-1(g0k(x))modp(x).
Consequently,|Tk(F)|≤1.
By (1) and (2), we get that |Tk(F)|≤1=degyF for any k∈ℕ.
(ii) We will prove this theorem by mathematical induction. Assume that(94)|Tk(F1)|≤degyF1,
for any F1∈ℝ[x] with degyF1≤n-1, we want to show
(95)|Tk(F)|≤degyF,
for any F∈ℝ[x] with degyF=n.
Letu=max{δp(F(x,c(x))):c(x)∈Tk(F)} and choose d(x)∈Tk(F) with
(96)δp(F(x,d(x)))=u.
Indeed,(97)δp(F(x,d(x)))≥δp(F(x,c(x)))for  anyc(x)∈Tk(F).
By the division rule, letF(x,y) be divided by y-d(x), giving us
(98)F(x,y)=(y-d(x))F1(x,y)+F(x,d(x)),
for some F1(x,y)∈ℝ[x,y] and degyF1(x,y)=n-1.
We want to show that(99)ifc(x)∈Tk(F)-{d(x)},thenc(x)∈Tk(F1).
For any c(x)∈Tk(F)-{d(x)}, by the definition of Tk(F), we have
(100)c(x)=a1(x)(p(x))k+b1(x),d(x)=a2(x)(p(x))k+b2(x),
for some b1(x), b2(x)∈Tk-1(F) and 0≤dega1(x), dega2(x)<degp(x). Since the elements d(x) and c(x) are distinct, so a1(x)≠a2(x) or b1(x)≠b2(x),
(a) Ifb1(x)≠b2(x), by the definition of b1(x) and b2(x), we have degb1(x), degb2(x)<degpk(x), so
(101)δp(b1(x)-b2(x))<k≤δp((a1(x)-a2(x))pk(x)).
Therefore, one has the following:(i)
δp(c(x)-d(x))=δp((a1(x)-a2(x))pk(x)+(b1(x)-b2(x)))=δp(b1(x)-b2(x))(by Lemma 14, (iv)),(ii)
δp(b1(x)-d(x))=δp((-a2(x))pk(x)+(b1(x)-b2(x)))=δp(b1(x)-b2(x))(by Lemma 14, (iv)),(iii)
δp(z(p(x))k+b1(x)-d(x))=δp((z-a2(x))pk(x)+(b1(x)-b2(x)))=δp(b1(x)-b2(x))(by Lemma 14, (iv)).
(b) ifb1(x)=b2(x), then a1(x)≠a2(x), since 0≤dega1(x), dega2(x)<degp(x), so (i)
δp(c(x)-d(x))=δp((a1(x)-a2(x))pk(x))=δp(a1(x)-a2(x))+k=k(by Lemma 14, (i)),(ii)
δp(b1(x)-d(x))=δp((-a2(x))pk(x))=δp(a2(x))+k=k(by Lemma 14, (i)),(iii)
δp(z(p(x))k+b1(x)-d(x))=δp((z-a2(x))pk(x)+(b1(x)-b2(x)))=δp(z-a2(x))+k=k(by Lemma 14, (i)).By the above equations, we obtain
(102)δp(c(x)-d(x))=δp(b1(x)-d(x))=δp(z(p(x))k+b1(x)-d(x)).
and by (D2) in Definition 15, we have
(103)δp(F(x,c(x)))>δp(F(x,z(p(x))k+b1(x))).
By (97) and (103), we have
(104)δpF(x,d(x))≥δp(F(x,c(x)))>δp(F(x,z(p(x))k+b1(x))).
Moreover, we have(105)δp(F(x,z(p(x))k+b1(x)))=δp((z(p(x))k+b1(x)-d(x))×F1(x,z(p(x))k+b1(x))+F(x,d(x)))(by(98))=δp((z(p(x))k+b1(x)-d(x))×F1(x,z(p(x))k+b1(x)))(by(104)and  Lemma14,(iv))=δp(z(p(x))k+b1(x)-d(x))+δp(F1(x,z(p(x))k+b1(x)))(byLemma14,(i)),(106)δp(F(x,c(x)))=δp((c(x)-d(x))F1(x,c(x))+F(x,d(x)))=δp((c(x)-d(x))F1(x,c(x)))(by(104)andLemma14,(iv))=δp(c(x)-d(x))+δp(F1(x,c(x)))(byLemma14,(i)).
From expression (106), we obtain
(107)δp(c(x)-d(x))+δp(F1(x,c(x)))=δp(F(x,c(x)))>δp(F(x,z(p(x))k+b1(x)))(by(104))=δp(z(p(x))k+b1(x)-d(x))+δp(F1(x,z(p(x))k+b1(x)))(by(105)).
From expression (102), that is, δp(c(x)-d(x))=δp(z(p(x))k+b1(x)-d(x)) and by canceling δp(c(x)-d(x)) to both sides of (107), it follows that
(108)δp(F1(x,c(x)))>δp(F1(x,z(p(x))k+b1(x))).
That is,c(x)∈Tk(F1). Then we have Tk(F)⊆Tk(F1)⋃‍{d(x)}. Therefore,
(109)|Tk(F)|≤|Tk(F1)|+1≤(n-1)+1=n.
By induction, the proof is completed.


## 5. Applications (As a Game Problem)

A quasi-fixed polynomial problem can be employed to many aspects of actuarial science, risk management, game theory, and so forth. We give an example from game theory as follows.Example 1.
LetA be an insurance company and B a customer. They make a game as follows.The companiesA and B enter into an s-year contract that within with an interest rate x=i. Assume each year B pays a total of fk(i) at k-th year to the insurance company A, 0≤k≤s and A prepare the asset S for B at the starting time of this contract. Assume the live inflation rate is y=1+r with r=r(i) dependent on the interest i. The total amount that B pays at thes-th year of this contract obeys the law of (year) motion about a quasi-fixed polynomial function:
(110)F(i,y(i))=fs(i)(1+r)s+fs-1(i)(1+r)s-1+⋯+f0(i).Nowx=i,y=y(x). p(x)=1+x+x2 is an irreducible polynomial. When the quasi-fixed polynomial equation
(111)F(i,y(i))=S(1+i+i2)m,m∈ℕ,
then B can obtain a premium
(112)S(1+i+i2)m.The second example concerns actuarial science.Example 2.
Traditionally, the disaster occurrence rate of all policies issued by general insurance companies is fixed. The actuary can use a variety of accounting systems to calculate the relationship between the interest rate and disaster occurrence for the policy. But, in general, measurement is very time consuming, and it would be preferable to use a simple mathematical calculation to estimate the relationship between the interest rate and disaster occurrence. In the following, we consider ans-year pure endowment contract.An insurance companyA signs a contract to some company B to the effect that if, in k-th year, a disaster occurs, A will pay an amount of money, ak, to B, that ak represents the compensation paid by A to B at the end of thek-th year, 0≤k≤s and the disaster occurrence rate is q. In calculating the insurance fee B should pay to A at the beginning of the contract, we assume that A gives a bonus interest rate, i+i2 to B.Question. How many dollars do B pay to A at the beginning of this contract and what is the relationship between the interest rate and disaster occurrence in the policy?Answer.
A pays ak dollars if the disaster occurs at the end of k-th year, k=1,2,…,s. Note that(1)
the probability of the disaster occurring in thek-th year is q(1-q)k,(2)
according to time factor, the value ofak dollars at the end of k-th year is equal to the value of ak(1+i)s-k dollars at the end of s-th year where s≥k, so the amount that A is expected to pay to B in the k-th year is
(113)ak(1+i)s-kq(1-q)k.Then the value of total amount thatA pays B at the end of s-th year is
(114)F(i,q)=a0(1+i)sq+a1(1+i)s-1q(1-q)+⋯+as.This can be rewritten as(115)(i)F(i,q)=fs(i)qs+fs-1(i)qs-1+⋯+f0(i).Moreover, we assume that the total amount thatB pays to A at the beginning of this contract is a. Then, by translation of the time factor, the value of this total amount that B pays to A by the end of the contract can be said to be
(116)(ii)a(1+i+i2)s+1.To balance each other, we set the values (i) and (ii) as equal. Thus, the relation equation becomes(117)F(i,q)=a(1+i+i2)s+1for  somea∈ℝ,
where q and i, respectively, denote the disaster occurrence rate and the interest rate.We can letx=i, y=q, p(x)=1+x+x2, and m=s+1, then the above problem can be rewritten as
(118)F(x,q)=apm(x)for  somea∈ℝ.This example explains a quasi-fixed (polynomial) problem concerning actuarial science.



---

*Source: 893045-2013-04-03.xml*