# Lower Bounds on Solutions of Quadratic Polynomials Defined over Finite Rings

Authors: Ali H. Hakami
Journal: International Journal of Mathematics and Mathematical Sciences
 (2015)

---

## Abstract

Letm be a positive integer and let Rm denote the ring Z/(m), and let Rmn denote the Cartesian product of n copies of Z/m. Let f(x) be a quadratic polynomial in Z[x1,…,xn]. In this paper, we are interested in giving lower bounds on the number of solutions of the quadratic polynomial f over the ring Rmn.


---

## Body

## 1. Introduction

LetRm=Z/(m) be a finite ring with m positive integer. Let f(x) be a quadratic polynomial in Z[x1,…,xn]. Write (1)fx=Qx+a·x+c,where a∈Zn, c∈Z, and Q(x) is a quadratic form given by(2)Qx=12xAxT,where A is a symmetric n×n matrix with integer entries. Throughout this paper (with the exception of Lemma 4), we will assume that gcd(det⁡A,m)=1. Let V be the algebraic subset of Rmn defined by (3)fx≡0mod⁡m.If d∣m and x,y∈Rmn, we will say that x≡y(mod⁡d) if x is congruent to y modulo the ideal dRm. For any subset S of Rmn and divisor d of m, let(4)ηS,d=s1,s2∈S×S:s1≡s2mod⁡d.Let ϕ denote the Euler phi-function, let τ(m) denote the number of distinct positive divisors of m, and for positive integers m and n set(5)Φnm=∑d>1d∣mϕdd-n/2.Considerable attention has been given to the problem of finding zeros of any polynomial over finite fields; see for example [1–8]. A special case of particular interest when the polynomial is quadratic over finite rings is studied in [9] by the author who obtained the following.Theorem 1.
For any subsetsS and T of Rmn, with |S|≤|T|, we have(6)S+T∩V≥m-1T-m-1S-1∑d>md∣mϕddn/2ηS,d1/2ηT,d1/2.In this paper, we will make the above result more precise whenS+T is a box of points in Rmn, that is, the image B¯ of a box B in Zn under the canonical mapping of Zn onto Rmn, where(7)B¯=x∈Zn:ai≤xi<ai+mi,for some ai,mi∈Z with 0<mi≤m, 1≤i≤n. In this case we obtain the following.Theorem 2.
Suppose thatn≥4. Let B¯ be a box in Rmn whose sides are all of the same length M<m; that is, let B¯ be the image of a box B as given in (7), where mi=M, 1≤i≤n. Put c=[(M+1)/2]. Then,(8)B¯∩V≥cnm1-Φnm-2nτmc-mm/2+1cn2ncm+1.In particular, if n≥6 and M≫m1/2+1/n, then B¯∩V is nonempty.The second part of Theorem2 follows immediately from Lemma 3 of the next section. The first part of the theorem will be proven in Section 3.


## 2. Auxiliary Lemmas

Lemma 3.
Ifn≥4, then for any integer m>1,(9)Φnm≤∏p∣m1+p1-n/2-1,where the product is over all primes p dividing m. In particular, if n≥6, then for all m>1, Φn(m)≤22-(n/2).Proof.
Lets=n/2 and set g(m)=∑d∣m‍ϕ(d)d-s, so that Φn(m)=g(m)-1. Since ϕ(d) and d-s are both multiplicative, g(m) is multiplicative. If p is a prime and e≥1, then (10)gpe=1+∑i=1epi-pi-1p-si=1+1-p-1∑i=1ep1-si<1+1-p-1p1-s∑i=0∞p1-si=1+p1-s1-p-11-p1-s≤1+p1-s.The last inequality follows since s≥2. The first part of the lemma now follows from the multiplicative property of g(m).
Now suppose thatn≥6. Again, letting s=n/2 we can say that(11)Φnm≤∑d=2∞ϕdd-s≤12s+23s+24s+∑d=5∞d1-s,since ϕ(d)<d. But(12)∑d=5∞d1-s<∫4∞x1-sdx=s-2-142-s.Thus, (13)Φnm<12s1+223s+12s-1+12s-4s-2≤12s·4,fors≥3.To prove Theorem2, we make use of exponential sums. Let em(x)=e(2πi/m)x. We will abbreviate complete sums ∑x∈Rmn‍() by simply ∑x‍(). Also we will need to use the following fundamental identity: for any y∈Rmn,(14)∑xemx·y=mnify=0,0ify≠0.Letf(x) and Q(x) be as defined by (1) and (2). By viewing Rmn as a Z-module, the Gauss sums(15)GmQ,y=∑x∈RmnemQx+y·x,Gmf,y=∑x∈Rmnemfx+y·xare well defined whether we take y∈Zn or y∈Rmn.For anyn×n matrix A with integer entries, we define kerm(A) by(16)kerm⁡A=x∈Rmn:AxT≡0Tmod⁡m.We need the following lemmas.Lemma 4 (see [10, Theorem4]).
LetQ(x) be a quadratic form given by (2), where now we allow A to be any symmetric integral matrix with even diagonal entries. Then, given y∈Rmn, the Gauss sum Gm(Q,y) is zero unless Q(x)+y·x≡0(mod⁡m) for all x∈kerm⁡(A), in which case GmQ,y|2=mnkerm⁡A|.Lemma 5.
Letf(x) be a quadratic polynomial as given by (1) with gcd(det⁡A,m)=1. Let y∈Zn, λ∈Z, λ≢0(mod⁡m), and set d=(λ,m). Then, (17)Gmλf,y=mdn/2ify≡0mod⁡d,0ify≢0mod⁡d.Proof.
By (1), we have (18)Gmλf,y=∑xemλfx+y·x=∑xemλQx+λa+y·x+λc=∑xemλQx+λa+y·x.Now λQ(x)=(1/2)x(λA)xT, so that by Lemma 4, Gm(λf,y)=0 unless y satisfies the following condition: (19)∀x∈kerm⁡λA,λa+y·x+λQx≡0mod⁡m.
Now(20)kerm⁡λA=x∈Rmn:λAxT≡0mod⁡m=x∈Rmn:AxT≡0mod⁡md,but as gcd(det⁡A,m)=1 we conclude that(21)kermλA=x∈Rmn:x≡0mod⁡md.Thus, setting x≡(m/d)tmod⁡m, we see that (19) is equivalent to saying that, for all t∈Zn, (22)λmda·t+mdy·t+λmd2Qt≡0mod⁡m.But λ(m/d)=m(λ/d)≡0mod⁡m and similarly λ(m/d)2=m(λ/d)(m/d)≡0(mod⁡m) so that (22) simplifies to the congruence (m/d)y·t≡0(mod⁡m); that is, y·t≡0(mod⁡d). Hence, y satisfies (19) if and only if, for all t∈Zn, y·t≡0(mod⁡d), that is y≡0(mod⁡d). If y≡0(mod⁡d) then by Lemma 4, and (21), we have(23)Gmλf,y2=m2kerm⁡λA=mndn.


## 3. Proof of Theorem2

LetS and T be subsets of Rmn, and let V be the set of points in Rmn satisfying f(x)≡0(mod⁡m). Let N be the number of triples (s,t,v)∈S×T×V such that s+t≡v(mod⁡m).Lemma 6.
LetN be the number of triples (s,t,v)∈S×T×V such that s+t≡v(mod⁡m). Then, for any subsets S and T of Rmn, with S⩽T we have (24)N-m-1ST≤m-1∑d>1d∣mϕdd-n/2dnηS,d1/2ηT,d1/2.Proof.
By the fundamental identity (14), (25)N=m-n∑x∈V∑s∈S∑t∈T∑yemy·s+t-x=m-n-1∑x∈Rmn∑λ∈Rmemλfx·∑s∈S∑t∈T∑yemy·s+t-x=m-n-1∑λ∑yΨy∑xemλfx-x,where(26)Ψy=∑s∈S∑t∈Temy·s+t.Peeling off the λ=0 term yields(27)N=m-1S·T+m-n-1∑λ≠0∑yΨy∑xemλfx-y·x.Thus (from (27)),(28)N-m-1S·T=m-n-1∑1≤d<md∣m∑1≤λ<mλ,m=d∑yΨy∑xemλfx-y·x,so that by Lemma 5, (29)N-m-1ST≤m-n-1∑d∣md<m∑1≤λ<mλ,m=dmn/2dn/2∑y∗⁡Ψy,where the sum ∑∗‍ on y is over all y≡0mod⁡d. On replacing d by m/d and ∑y∗‍ by ∑y∗∗‍, the sum over all y≡0(mod⁡(m/d)), we obtain(30)N-m-1ST≤m-n/2-1∑d∣md<mϕmddn/2∑y∗⁡Ψy=m-1∑d>1d∣mϕdd-n/2∑y∗∗⁡Ψy.
Now,(31)∑y∗∗⁡ΨyΨy=∑y∗∗⁡∑s∈Semy·s∑t∈Temy·t≤∑y∗∗⁡∑s∈Semy·s21/2·∑y∗∗⁡∑t∈Temy·t21/2.Setting y≡(m/d)u(mod⁡m) and letting u run through a complete set of representatives for Rdn, we can say (32)∑y∗∗⁡∑t∈Temy·t2=∑y∗∗⁡∑s1∈S∑s2∈Semy·s1-s2=∑s1∈S∑s2∈S∑y∗∗⁡emy·s1-s2=∑s1∈S∑s2∈S∑u∈Rdnemmdu·s1-s2=∑s1∈S∑s2∈S∑uedu·s1-s2=dnηS,d.Thus, by (31),(33)∑y∗∗⁡Ψy≤dnηS,d1/2ηT,d1/2,and therefore, by (30), (34)N-m-1ST≤m-1∑d>1d∣mϕdd-n/2dnηS,d1/2ηT,d1/2.Proof of Theorem2.
Let(35)B=x∈Zn:ai≤xi<ai+M,1≤i≤n,S=x∈Zn:0≤xi<c,T=S+a1,a2,…,an,for some ai∈Z, 1≤i≤n, where c=(M+1)/c. Let B¯, S¯, and T¯ be the images of B, S, and T in Rmn under the canonical mapping of Zn onto Rmn. Then, S¯+T¯⊂B¯ and |S¯|=|T¯|=(M+1)/cn≥2-n|B¯|. We claim that for any divisor d of m,(36)ηS¯,d≤cncd+1n,and that the same inequality holds for η(T¯,d). Let s=(s1,…,sn) be a fixed point in S. If u=(u1,…,un) is a point in S such that u≡s(mod⁡d), then ui=si+dki, for some ki∈Z, 1≤i≤n. Since 0≤ui<c, there are at most c/d+1 choices for each ui, and thus at most c/d+1n choices for u. Since |S|=cn, we obtain (36). It is clear that η(S¯,d)=η(T¯,d) so that (36) holds also for η(T¯,d).
We now apply Theorem1 with S and T replaced by the sets S¯ and T¯ just defined. We will abbreviate the sum ∑d>1,d∣m by simple ∑∗‍. From Lemma 6 and (36) we have (37)N-m-1ST≤m-1∑∗⁡ϕddn/2cncd+1n≤m-1∑∗⁡ϕddn/2cnd-nc+dn=m-1cn∑∗⁡ϕdd-n/2cnc+dn.Now, since (c+d)n≤cn+2n(cn-1d+cdn-1)+dn, we have(38)N-m-1ST≤m-1c2n∑∗⁡ϕdd-n/2+m-12nc2n-1∑∗⁡ϕdd1-n/2+m-12ncn+1∑∗⁡ϕddn/2-1+m-1cn∑∗⁡ϕddn/2.The first sum on the right-hand side of (38) is just Φn(m). We make crude estimates for the remaining sums. For n≥4 we have(39)∑∗⁡ϕdd1-n/2≤∑∗⁡ϕdd-1≤∑∗⁡1<τm,∑∗⁡ϕddn/2-1≤mn/2-1∑∗⁡ϕd≤mn/2-1·m=mn/2,∑∗⁡ϕddn/2≤mn/2∑∗⁡ϕd≤mn/2+1.Thus, by (38), we see that (40)N≥m-1c2n-m-1c2nΦnm-m-12nc2n-1τm-m-12ncn+1mn/2-m-1cnmn/2+1=m-1c2n1-Φnm-2nc-1τm-c-nmn/2+12ncm-1+1.Theorem 2 now follows from the observation that(41)B¯∩V≥S¯∩T¯∩V≥NS-1=Nc-n.


## 4. Remarks

(1)
It is clear from (39) and Lemma 3 that if n≥8 then in the statement of Theorem 2 we can replace τ(m) by 23-(n/2).
(2)
Letf(x) be given by (1), let V be the set of zeros of f(x) in Rmn, and again suppose that gcd(det⁡A,m)=1. Lemma 5 provides us with an easy means of estimating |V|. For n≥4, we obtain (42)V=mn-1∏p∣m1+θpp1-n/2,where the product is over all primes p dividing m, and for each such p, θp is a real number of absolute value ≤1. Equation (42) follows from the observation that (43)V=m-1∑x∈Rmn∑λ=0m-1eλfx=mn-1+m-1∑λ=1m-1∑xeλfx.By Lemma 5, we then have(44)V=mn-1+θmmn/2-1∑1≤d<md∣mϕmddn/2,for some θm∈R, with |θm|≤1. Since(45)Φnm=∑d>1d∣mϕdd-n/2=∑1≤d<md∣mϕmddmn/2,we obtain(46)V=mn-11+θmΦnm.To obtain (42), we apply (46) in turn to each prime power dividing m and use the Chinese remainder theorem to compute |V|. That is, for each divisor d of m, we let v(d) be the number of points in Rdn satisfying the congruence f(x)≡0mod⁡d. Consequently, if m=∏i=1s‍piei then v(m)=∏i=1s‍v(piei). Thus, by (46), we have(47)V=vm=∏i=1spiein-11+θiΦnpiei,for some θi∈R with |θi|≤1, 1≤i≤s, and by Lemma 3 we have(48)Φnpe≤p1-n/2,for any prime power pe, when n≥4. Equation (42) is now immediate.Equation (42) indicates that we obtain roughly the expected quota of zeros for f(x), namely, mn-1, when gcd(det⁡A,m)=1. When gcd(det⁡A,m)≠1, this is no longer the case. For example, suppose that m=pq, where p and q are distinct primes. Let α be quadratic nonresidue (mod⁡p), let β be a quadratic nonresidue (mod⁡q), and let f(x)=f(x1,x2,x3,x4) be defined by(49)fx=px12-βx22+qx32-αx42.If x is an integral solution of the congruence f(x)≡0(mod⁡m) then x12-βx22≡0(mod⁡q) and x32-αx42≡0(mod⁡p), so that x1≡x2≡0(mod⁡q) and x3≡x4≡0(mod⁡p). Thus, if V is the set of points in Rm4 satisfying f(x)≡0(mod⁡m), then |V|=p2q2=m2, rather than expected quota of m3. This example indicates that Theorem 2 does not hold when gcd(det⁡A,m)≠1.We have not been able to obtain an analogue of Theorem2 when gcd(det⁡A,m)≠1. The main difficulty is that kerm(λA) no longer leads to such a simple description as in the case when gcd(det⁡A,m)=1; see (21). To overcome this difficulty, one may be able to use the description of kerm(λA) given in section 4 of [11] which involved the invariant factors of A.



---

*Source: 305730-2015-06-10.xml*