Manifest. This is an answer to MathOverflow question #68595 (which also gives a new answer to #66959). It was produced by GPT-6 Astra (Researcher subscription). The main proof was found in one 3-minute shot, and expanded and polished over several rounds of edits. I have proofread the whole text except for Section § 8 . This text is in the public domain. –Darij
Statement and finite differences
Start with an integer-valued function on the integers. Replace each value by the average of that value and the next p − 1 p-1 p − 1 p p p [9 ] , concerns this process for p = 2 p = 2 p = 2 p p p p p p
We begin by fixing the notation. We consider the Q \mathbb{Q} Q Q Z \mathbb{Q}^{\mathbb{Z}} Q Z f : Z → Q f : \mathbb{Z} \to\mathbb{Q} f : Z → Q
( … , f ( − 2 ) , f ( − 1 ) , f ( 0 ) , f ( 1 ) , f ( 2 ) , … ) (\ldots, f(-2), f(-1), f(0), f(1), f(2), \ldots) ( … , f ( − 2 ) , f ( − 1 ) , f ( 0 ) , f ( 1 ) , f ( 2 ) , … ) (infinite in both directions). Such a function f : Z → Q f:\mathbb{Z}\to\mathbb{Q} f : Z → Q integral if all its values f ( n ) f(n) f ( n ) f ∈ Z Z f\in\mathbb{Z}^{\mathbb{Z}} f ∈ Z Z Z Z \mathbb{Z}^{\mathbb{Z}} Z Z Z \mathbb{Z} Z Q Z \mathbb{Q}^{\mathbb{Z}} Q Z
We shall consider linear (that is, Q \mathbb{Q} Q Q Z \mathbb{Q}^{\mathbb{Z}} Q Z A ( a f + b g ) = a A f + b A g A(af+bg)=aAf+bAg A ( a f + b g ) = a A f + b A g a , b a,b a , b f , g f,g f , g A A A f ∈ Q Z f\in\mathbb{Q}^{\mathbb{Z}} f ∈ Q Z A f ( n ) Af(n) A f ( n ) ( A f ) ( n ) (Af)(n) ( A f ) ( n )
Fix a prime p p p F p : Q Z → Q Z F_p:\mathbb{Q}^{\mathbb{Z}}\to\mathbb{Q}^{\mathbb{Z}} F p : Q Z → Q Z averaging operator ) by
( F p f ) ( n ) = 1 p ∑ r = 0 p − 1 f ( n + r ) for all f ∈ Q Z and n ∈ Z . (F_pf)(n)=\frac{1}{p}\sum_{r=0}^{p-1}f(n+r)\qquad\text{for all }f\in\mathbb{Q}^{\mathbb{Z}}\text{ and }n\in\mathbb{Z}. ( F p f ) ( n ) = p 1 r = 0 ∑ p − 1 f ( n + r ) for all f ∈ Q Z and n ∈ Z . That is, F p F_p F p f f f f ( n ) f(n) f ( n ) p p p f ( n ) f(n) f ( n ) f : Z → Q f:\mathbb{Z}\to\mathbb{Q} f : Z → Q f p : Z → Q f^p:\mathbb{Z}\to\mathbb{Q} f p : Z → Q
f p ( n ) = f ( n ) p for all n ∈ Z . f^p(n)=f(n)^p\qquad\text{for all }n\in\mathbb{Z}. f p ( n ) = f ( n ) p for all n ∈ Z . Operator powers mean repeated application: F p 2 f = F p ( F p f ) F_p^2f=F_p(F_pf) F p 2 f = F p ( F p f ) F p 0 f = f F_p^0f=f F p 0 f = f f p f^p f p
A function f : Z → Q f:\mathbb{Z}\to\mathbb{Q} f : Z → Q ℓ \ell ℓ average-integral for a given nonnegative integer ℓ \ell ℓ F p k f F_p^kf F p k f 0 ≤ k ≤ ℓ 0\leq k\leq\ell 0 ≤ k ≤ ℓ ℓ \ell ℓ f f f k = 0 k=0 k = 0 F p k f = F p 0 f = f F_p^kf=F_p^0f=f F p k f = F p 0 f = f ℓ \ell ℓ ℓ \ell ℓ
We say that f : Z → Q f:\mathbb{Z}\to\mathbb{Q} f : Z → Q average-integral if F p k f F_p^kf F p k f k ≥ 0 k\geq0 k ≥ 0 ℓ \ell ℓ ℓ ≥ 0 \ell\geq0 ℓ ≥ 0 p = 2 p=2 p = 2 f : n ↦ 2 n f:n\mapsto2n f : n ↦ 2 n k k k F p k f F_p^kf F p k f n ↦ 2 n + k n\mapsto2n+k n ↦ 2 n + k
We will prove the following two properties of ℓ \ell ℓ
Theorem 1.1. Let 0 ≤ ℓ ≤ p 0\leq\ell\leq p 0 ≤ ℓ ≤ p f : Z → Z f:\mathbb{Z}\to\mathbb{Z} f : Z → Z ℓ \ell ℓ f p f^p f p ℓ \ell ℓ
Theorem 1.2. Let ℓ ≥ 0 \ell\geq0 ℓ ≥ 0
For p = 2 p=2 p = 2 ℓ \ell ℓ
For p = 3 p=3 p = 3 f f f ℓ \ell ℓ f 3 f^3 f 3 ℓ \ell ℓ
Corollary 1.3. The set of all average-integral functions is closed under pointwise products for p = 2 p=2 p = 2 f ↦ f 3 f\mapsto f^3 f ↦ f 3
Theorem 1.1 answers a question asked in [1 ] . Corollary 1.3 was already discussed in [2 ] . For primes p > 3 p>3 p > 3 p p p p + 1 p+1 p + 1
Our proofs use several ideas suggested by Zarathustra Brady (“zeb” on MathOverflow) in his answer to [2 ] . They have two major ingredients in common. First we translate integrality of averages into divisibility of finite differences. Then we use polynomial interpolation to study these divisibilities on a finite interval. This proves Theorem 1.1 in § 3 . To handle arbitrarily many rounds for p = 2 , 3 p=2,3 p = 2 , 3 Theorem 1.2 and Corollary 1.3), we will need a fuller description of the polynomials that remain integral under averaging. Our main tool is the finite difference operator Δ : Q Z → Q Z \Delta:\mathbb{Q}^{\mathbb{Z}}\to\mathbb{Q}^{\mathbb{Z}} Δ : Q Z → Q Z
Δ f ( n ) = f ( n + 1 ) − f ( n ) for all f ∈ Q Z and n ∈ Z . \Delta f(n)=f(n+1)-f(n) \qquad\text{for all } f\in\mathbb{Q}^{\mathbb{Z}}\text{ and }n\in\mathbb{Z}. Δ f ( n ) = f ( n + 1 ) − f ( n ) for all f ∈ Q Z and n ∈ Z . Unlike averaging, taking a finite difference always preserves integrality; i.e., we have Δ f ∈ Z Z \Delta f\in\mathbb{Z}^{\mathbb{Z}} Δ f ∈ Z Z f ∈ Z Z f\in\mathbb{Z}^{\mathbb{Z}} f ∈ Z Z
Define the shift operator E : Q Z → Q Z E:\mathbb{Q}^{\mathbb{Z}}\to\mathbb{Q}^{\mathbb{Z}} E : Q Z → Q Z
E f ( n ) = f ( n + 1 ) for all f ∈ Q Z and n ∈ Z . Ef(n)=f(n+1) \qquad\text{for all } f\in\mathbb{Q}^{\mathbb{Z}}\text{ and }n\in\mathbb{Z}. E f ( n ) = f ( n + 1 ) for all f ∈ Q Z and n ∈ Z . Thus, Δ = E − id \Delta=E-\operatorname{id} Δ = E − id F p F_p F p E E E Δ \Delta Δ Q \mathbb{Q} Q Q Z \mathbb{Q}^{\mathbb{Z}} Q Z Z Z \mathbb{Z}^{\mathbb{Z}} Z Z f : Z → Q f:\mathbb{Z}\to\mathbb{Q} f : Z → Q
Δ f ( n ) = f ( n + 1 ) − f ( n ) , Δ 2 f ( n ) = f ( n + 2 ) − 2 f ( n + 1 ) + f ( n ) . \Delta f(n)=f(n+1)-f(n), \qquad\Delta^2f(n)=f(n+2)-2f(n+1)+f(n). Δ f ( n ) = f ( n + 1 ) − f ( n ) , Δ 2 f ( n ) = f ( n + 2 ) − 2 f ( n + 1 ) + f ( n ) . Set q = p − 1 q=p-1 q = p − 1 Δ j f ∈ p k Z Z \Delta^j f\in p^k\mathbb{Z}^{\mathbb{Z}} Δ j f ∈ p k Z Z p k p^k p k Δ j f ( n ) \Delta^j f(n) Δ j f ( n ) n n n q = p − 1 q=p-1 q = p − 1 p = 3 p=3 p = 3 f f f 3 ∣ Δ 2 f ( n ) 3\mid\Delta^2f(n) 3 ∣ Δ 2 f ( n ) 9 ∣ Δ 4 f ( n ) 9\mid\Delta^4f(n) 9 ∣ Δ 4 f ( n ) n n n
Lemma 1.4 (Difference criterion). For a function f : Z → Q f:\mathbb{Z}\to\mathbb{Q} f : Z → Q ℓ ≥ 0 \ell\geq0 ℓ ≥ 0
The function f f f ℓ \ell ℓ
We have Δ k q f ∈ p k Z Z \Delta^{kq}f\in p^k\mathbb{Z}^{\mathbb{Z}} Δ k q f ∈ p k Z Z 0 ≤ k ≤ ℓ 0\leq k\leq\ell 0 ≤ k ≤ ℓ
We have Δ j f ∈ p ⌊ j / q ⌋ Z Z \Delta^j f\in p^{\lfloor j/q\rfloor}\mathbb{Z}^{\mathbb{Z}} Δ j f ∈ p ⌊ j / q ⌋ Z Z 0 ≤ j ≤ ℓ q 0\leq j\leq\ell q 0 ≤ j ≤ ℓ q
Proof. We assume that f f f 2
We first compare one averaging step with q q q A ( X ) = ∑ i a i X i A(X)=\sum_i a_iX^i A ( X ) = ∑ i a i X i A ( E ) A(E) A ( E ) ∑ i a i E i \sum_i a_iE^i ∑ i a i E i ( E i f ) ( n ) = f ( n + i ) (E^i f)(n)=f(n+i) ( E i f ) ( n ) = f ( n + i ) F p F_p F p
F p = 1 p ( id + E + ⋯ + E p − 1 ) . (1) F_p=\frac{1}{p}\left(\operatorname{id}+E+\cdots+E^{p-1}\right). \tag*{(1)} F p = p 1 ( id + E + ⋯ + E p − 1 ) . (1) Hence,
p F p = id + E + ⋯ + E p − 1 . (2) pF_p=\operatorname{id}+E+\cdots+E^{p-1}. \tag*{(2)} p F p = id + E + ⋯ + E p − 1 . (2) Moreover, from Δ = E − i d \Delta= E - \mathrm{id} Δ = E − id q = p − 1 q = p - 1 q = p − 1 Δ q = ( E − i d ) p − 1 \Delta^{q} = (E - \mathrm{id})^{p-1} Δ q = ( E − id ) p − 1
1 + X + ⋯ + X p − 1 ≡ ( X − 1 ) p − 1 ( m o d p ) . (3) 1 + X + \cdots+ X^{p-1} \equiv(X - 1)^{p-1} \pmod{p}. \tag*{(3)} 1 + X + ⋯ + X p − 1 ≡ ( X − 1 ) p − 1 ( mod p ) . (3) To see this congruence, reduce modulo p p p X p − 1 = ( X − 1 ) p X^{p} - 1 = (X - 1)^{p} X p − 1 = ( X − 1 ) p X − 1 X - 1 X − 1 F p [ X ] \mathbb{F}_{p}[X] F p [ X ] (3) . That is, in Z [ X ] \mathbb{Z}[X] Z [ X ]
1 + X + ⋯ + X p − 1 = ( X − 1 ) p − 1 + p B ( X ) for some B ( X ) ∈ Z [ X ] . 1 + X + \cdots+ X^{p-1} = (X - 1)^{p-1} + pB(X) \qquad\text{for some } B(X) \in\mathbb{Z}[X]. 1 + X + ⋯ + X p − 1 = ( X − 1 ) p − 1 + pB ( X ) for some B ( X ) ∈ Z [ X ] . Now substitute the shift operator E E E X X X
p F p = Δ q + p B ( E ) pF_{p} = \Delta^{q} + pB(E) p F p = Δ q + pB ( E ) (since p F p = i d + E + ⋯ + E p − 1 pF_{p} = \mathrm{id} + E + \cdots+ E^{p-1} p F p = id + E + ⋯ + E p − 1 Δ q = ( E − i d ) p − 1 \Delta^{q} = (E - \mathrm{id})^{p-1} Δ q = ( E − id ) p − 1
D = Δ q p (4) D = \frac{\Delta^{q}}{p} \tag*{(4)} D = p Δ q (4) and dividing by p p p
F p = D + B ( E ) , (5) F_{p} = D + B(E), \tag*{(5)} F p = D + B ( E ) , (5) so that D = F p − B ( E ) D = F_{p} - B(E) D = F p − B ( E ) B ( E ) = F p − D B(E) = F_{p} - D B ( E ) = F p − D B ( E ) B(E) B ( E ) Z Z \mathbb{Z}^{\mathbb{Z}} Z Z f f f (5) therefore shows that F p f F_{p}f F p f D f Df D f p = 3 p = 3 p = 3 B ( X ) = X B(X) = X B ( X ) = X
F 3 f ( n ) = f ( n + 1 ) + f ( n + 2 ) − 2 f ( n + 1 ) + f ( n ) 3 . F_{3}f(n) = f(n + 1) + \frac{f(n + 2) - 2f(n + 1) + f(n)}{3}. F 3 f ( n ) = f ( n + 1 ) + 3 f ( n + 2 ) − 2 f ( n + 1 ) + f ( n ) . The numerator in the fraction is Δ 2 f ( n ) \Delta^{2}f(n) Δ 2 f ( n )
The same comparison works for every iterate. All three operators F p F_{p} F p D D D B ( E ) B(E) B ( E ) E E E F p i f F_{p}^{i}f F p i f 0 ≤ i ≤ k 0 \leq i \leq k 0 ≤ i ≤ k D = F p − B ( E ) D = F_{p} - B(E) D = F p − B ( E )
D k f = ( F p − B ( E ) ) k f = ∑ i = 0 k ( k i ) ( − B ( E ) ) k − i F p i f D^{k}f = (F_{p} - B(E))^{k}f = \sum_{i=0}^{k} \binom{k}{i} \left(-B(E)\right)^{k-i}F_{p}^{i}f D k f = ( F p − B ( E ) ) k f = i = 0 ∑ k ( i k ) ( − B ( E ) ) k − i F p i f is integral as well: each summand is obtained from an integral function (viz., F p i f F_{p}^{i}f F p i f B ( E ) B(E) B ( E ) Z Z \mathbb{Z}^{\mathbb{Z}} Z Z D i f D^{i}f D i f 0 ≤ i ≤ k 0 \leq i \leq k 0 ≤ i ≤ k F p = D + B ( E ) F_{p} = D + B(E) F p = D + B ( E ) D D D B ( E ) B(E) B ( E )
F p k f = ( D + B ( E ) ) k f = ∑ i = 0 k ( k i ) B ( E ) k − i D i f . F_{p}^{k}f = (D + B(E))^{k}f = \sum_{i=0}^{k} \binom{k}{i} B(E)^{k-i}D^{i}f. F p k f = ( D + B ( E ) ) k f = i = 0 ∑ k ( i k ) B ( E ) k − i D i f . Each D i f D^i f D i f B ( E ) B(E) B ( E ) ( k i ) \binom{k}{i} ( i k ) F p k f F_p^k f F p k f F p k f F_p^k f F p k f 0 ≤ k ≤ ℓ 0 \le k \le\ell 0 ≤ k ≤ ℓ D k f D^k f D k f 0 ≤ k ≤ ℓ 0 \le k \le\ell 0 ≤ k ≤ ℓ D k f = Δ k q f / p k D^k f = \Delta^{kq}f/p^k D k f = Δ k q f / p k
It remains to show that conditions 2 and 3 are equivalent. Clearly, condition 3 implies condition 2 (by applying it to j = k q j=kq j = k q j j j q q q j j j q q q j j j j = k q + r j=kq+r j = k q + r 0 ≤ r < q 0 \le r < q 0 ≤ r < q k = ⌊ j / q ⌋ ≤ ℓ k=\lfloor j/q\rfloor\le\ell k = ⌊ j / q ⌋ ≤ ℓ Δ k q f = p k g \Delta^{kq}f=p^k g Δ k q f = p k g g g g r r r Δ j f = p k Δ r g \Delta^j f=p^k\Delta^r g Δ j f = p k Δ r g j = k q + r j=kq+r j = k q + r p k p^k p k Δ j f ∈ p k Z Z = p ⌊ j / q ⌋ Z Z \Delta^j f \in p^k\mathbb{Z}^{\mathbb{Z}}=p^{\lfloor j/q\rfloor}\mathbb{Z}^{\mathbb{Z}} Δ j f ∈ p k Z Z = p ⌊ j / q ⌋ Z Z
The polynomial congruence
Our next step is a statement about polynomials. We will later use it on a polynomial that agrees with f f f p p p
Let R = Z ( p ) R=\mathbb{Z}_{(p)} R = Z ( p ) Q \mathbb{Q} Q r / s r/s r / s r , s ∈ Z r,s\in\mathbb{Z} r , s ∈ Z p p p p = 3 p=3 p = 3 1 / 2 1/2 1/2 R R R 1 / 3 1/3 1/3 a ∈ p k R a\in p^kR a ∈ p k R k k k a a a k k k p p p a a a p k p^k p k
For a nonzero rational number a a a v p ( a ) v_p(a) v p ( a ) p p p v p ( 0 ) = + ∞ v_p(0)=+\infty v p ( 0 ) = + ∞ a ∈ p k R a\in p^kR a ∈ p k R v p ( a ) ≥ k v_p(a)\ge k v p ( a ) ≥ k
v p ( t ! ) = ∑ i ≥ 1 ⌊ t p i ⌋ for all t ≥ 0. (6) v_p(t!)=\sum_{i\ge1}\left\lfloor\frac{t}{p^i}\right\rfloor\qquad\text{for all }t\ge0. \tag*{(6)} v p ( t !) = i ≥ 1 ∑ ⌊ p i t ⌋ for all t ≥ 0. (6) Indeed, among 1 , … , t 1,\ldots,t 1 , … , t p p p p p p p 2 p^2 p 2
We use the same operators E E E Δ \Delta Δ F p F_p F p
( E H ) ( x ) = H ( x + 1 ) , ( Δ H ) ( x ) = H ( x + 1 ) − H ( x ) , ( F p H ) ( x ) = 1 p ∑ r = 0 p − 1 H ( x + r ) . (EH)(x)=H(x+1),\qquad(\Delta H)(x)=H(x+1)-H(x),\qquad(F_pH)(x)=\frac{1}{p}\sum_{r=0}^{p-1}H(x+r). ( E H ) ( x ) = H ( x + 1 ) , ( Δ H ) ( x ) = H ( x + 1 ) − H ( x ) , ( F p H ) ( x ) = p 1 r = 0 ∑ p − 1 H ( x + r ) . These definitions are compatible with evaluation at integers. More precisely, for any H ∈ Q [ x ] H\in\mathbb{Q}[x] H ∈ Q [ x ] ev ( H ) ∈ Q Z \operatorname{ev}(H)\in\mathbb{Q}^{\mathbb{Z}} ev ( H ) ∈ Q Z n ↦ H ( n ) n\mapsto H(n) n ↦ H ( n )
ev ( A H ) = A ev ( H ) for A = E , Δ , F p . (7) \operatorname{ev}(AH)=A\operatorname{ev}(H)\qquad\text{for }A=E,\Delta,F_p. \tag*{(7)} ev ( A H ) = A ev ( H ) for A = E , Δ , F p . (7) For example, both sides for A = Δ A=\Delta A = Δ n n n H ( n + 1 ) − H ( n ) H(n+1)-H(n) H ( n + 1 ) − H ( n )
For finite differences, a convenient R R R R [ x ] R[x] R [ x ] falling factorials
( x ) j = x ( x − 1 ) ⋯ ( x − j + 1 ) for all j ≥ 0. (x)_j = x(x-1)\cdots(x-j+1) \qquad\text{for all } j \ge0. ( x ) j = x ( x − 1 ) ⋯ ( x − j + 1 ) for all j ≥ 0. The first few are ( x ) 0 = 1 (x)_0 = 1 ( x ) 0 = 1 ( x ) 1 = x (x)_1 = x ( x ) 1 = x ( x ) 2 = x ( x − 1 ) (x)_2 = x(x-1) ( x ) 2 = x ( x − 1 ) ( x ) 3 = x ( x − 1 ) ( x − 2 ) (x)_3 = x(x-1)(x-2) ( x ) 3 = x ( x − 1 ) ( x − 2 ) 1 1 1 R [ x ] R[x] R [ x ]
x 2 = ( x ) 2 + ( x ) 1 , x 3 = ( x ) 3 + 3 ( x ) 2 + ( x ) 1 . x^2 = (x)_2 + (x)_1,\qquad x^3 = (x)_3 + 3(x)_2 + (x)_1. x 2 = ( x ) 2 + ( x ) 1 , x 3 = ( x ) 3 + 3 ( x ) 2 + ( x ) 1 . So each polynomial P ∈ R [ x ] P \in R[x] P ∈ R [ x ] ∑ j ≥ 0 c j ( x ) j \sum_{j\ge0} c_j(x)_j ∑ j ≥ 0 c j ( x ) j c j ∈ R c_j \in R c j ∈ R c j = 0 c_j = 0 c j = 0 j j j c j c_j c j falling-factorial coefficients of P P P R R R
The falling factorials also satisfy Δ ( x ) 0 = 0 \Delta(x)_0 = 0 Δ ( x ) 0 = 0
Δ ( x ) j = j ( x ) j − 1 for all j ≥ 1. (8) \Delta(x)_j = j(x)_{j-1} \qquad\text{for all } j \ge1. \tag*{(8)} Δ ( x ) j = j ( x ) j − 1 for all j ≥ 1. (8) This follows by factoring ( x ) j − 1 (x)_{j-1} ( x ) j − 1 ( x + 1 ) j − ( x ) j (x+1)_j - (x)_j ( x + 1 ) j − ( x ) j ( x + 1 ) − ( x − j + 1 ) = j (x+1) - (x-j+1) = j ( x + 1 ) − ( x − j + 1 ) = j (8) and setting x = 0 x = 0 x = 0 H ( x ) = ∑ j ≥ 0 c j ( x ) j H(x) = \sum_{j\ge0} c_j(x)_j H ( x ) = ∑ j ≥ 0 c j ( x ) j
Δ m H ( 0 ) = m ! c m for all m ≥ 0. (9) \Delta^m H(0) = m!c_m \qquad\text{for all } m \ge0. \tag*{(9)} Δ m H ( 0 ) = m ! c m for all m ≥ 0. (9) Indeed, terms c j ( x ) j c_j(x)_j c j ( x ) j j < m j < m j < m m m m j > m j > m j > m x x x j = m j = m j = m x = 0 x = 0 x = 0
We first isolate a fact about falling-factorial coefficients over F p \mathbb{F}_p F p p p p F p [ x ] \mathbb{F}_p[x] F p [ x ] P ∈ F p [ x ] P \in\mathbb{F}_p[x] P ∈ F p [ x ] [ ( x ) i ] P [(x)_i]P [( x ) i ] P ( x ) i (x)_i ( x ) i P P P [ ( x ) i ] P = 0 [(x)_i]P = 0 [( x ) i ] P = 0 i < 0 i < 0 i < 0
Multiplication by x p − x x^p-x x p − x p p p
Lemma 2.1. Put y = x p − x ∈ F p [ x ] y = x^p-x \in\mathbb{F}_p[x] y = x p − x ∈ F p [ x ]
We have
y ( x ) i = ( x ) p + i for all i ≥ 0. (10) y(x)_i = (x)_{p+i} \qquad\text{for all } i \ge0. \tag*{(10)} y ( x ) i = ( x ) p + i for all i ≥ 0. (10) More generally, we have
y a ( x ) j = ( x ) a p + j for all a , j ≥ 0. (11) y^a(x)_j = (x)_{ap+j} \qquad\text{for all } a,j \ge0. \tag*{(11)} y a ( x ) j = ( x ) a p + j for all a , j ≥ 0. (11) For every P ∈ F p [ x ] P \in\mathbb{F}_p[x] P ∈ F p [ x ]
[ ( x ) i ] ( y P ) = [ ( x ) i − p ] P for all integers i . (12) [(x)_i](yP) = [(x)_{i-p}]P \qquad\text{for all integers } i. \tag*{(12)} [( x ) i ] ( y P ) = [( x ) i − p ] P for all integers i . (12) More generally, for every P ∈ F p [ x ] P \in\mathbb{F}_p[x] P ∈ F p [ x ]
[ ( x ) i ] ( y a P ) = [ ( x ) i − a p ] P for all a ≥ 0 and all integers i . (13) [(x)_i](y^aP)=[(x)_{i-ap}]P\qquad\text{for all }a\ge0\text{ and all integers }i. \tag*{(13)} [( x ) i ] ( y a P ) = [( x ) i − a p ] P for all a ≥ 0 and all integers i . (13) Proof. We first recall the classical finite-field property
x ( x − 1 ) ⋯ ( x − p + 1 ) = x p − x , x(x-1)\cdots(x-p+1)=x^p-x, x ( x − 1 ) ⋯ ( x − p + 1 ) = x p − x , which holds because both sides are monic polynomials of degree p p p F p \mathbb{F}_p F p [8 Section 10] , where it is used in an umbral proof of Touchard’s congruence for Bell numbers. Now, we study the product ( x ) p + i = x ( x − 1 ) ⋯ ( x − p − i + 1 ) (x)_{p+i}=x(x-1)\cdots(x-p-i+1) ( x ) p + i = x ( x − 1 ) ⋯ ( x − p − i + 1 ) p p p
x ( x − 1 ) ⋯ ( x − p + 1 ) = x p − x = y . x(x-1)\cdots(x-p+1)=x^p-x=y. x ( x − 1 ) ⋯ ( x − p + 1 ) = x p − x = y . Its remaining i i i x − p , x − p − 1 , … , x − p − i + 1 x-p,x-p-1,\ldots,x-p-i+1 x − p , x − p − 1 , … , x − p − i + 1 p p p x , x − 1 , … , x − i + 1 x,x-1,\ldots,x-i+1 x , x − 1 , … , x − i + 1 ( x ) i (x)_i ( x ) i y ( x ) i = ( x ) p + i y(x)_i=(x)_{p+i} y ( x ) i = ( x ) p + i (10) (including the case i = 0 i=0 i = 0 (10) successively a a a (11) .
To prove (12) , write P = ∑ j ≥ 0 c j ( x ) j P=\sum_{j\ge0}c_j(x)_j P = ∑ j ≥ 0 c j ( x ) j
y P = ∑ j ≥ 0 c j ( x ) p + j . yP=\sum_{j\ge0}c_j(x)_{p+j}. y P = j ≥ 0 ∑ c j ( x ) p + j . Thus the ( x ) i (x)_i ( x ) i c i − p c_{i-p} c i − p i ≥ p i\ge p i ≥ p (12) , with our convention for negative indices. To prove (13) , apply (12) successively a a a
We now use this shift to describe which coefficients of a p p p p 2 p^2 p 2
Lemma 2.2. Let H ∈ F p [ x ] H\in\mathbb{F}_p[x] H ∈ F p [ x ] Q Q Q H H H x p − x x^p-x x p − x deg Q ≤ d \deg Q\le d deg Q ≤ d 0 ≤ d < p 0\le d<p 0 ≤ d < p
H ( x ) p = ∑ j ≥ 0 γ j ( x ) j with γ j ∈ F p H(x)^p=\sum_{j\ge0}\gamma_j(x)_j\qquad\text{with }\gamma_j\in\mathbb{F}_p H ( x ) p = j ≥ 0 ∑ γ j ( x ) j with γ j ∈ F p (so that γ j \gamma_j γ j ( x ) j (x)_j ( x ) j H ( x ) p H(x)^p H ( x ) p j ≥ 0 j\ge0 j ≥ 0
γ a p + b = 0 for all 0 ≤ a , b < p with a + b > d . \gamma_{ap+b}=0\qquad\text{for all }0\le a,b<p\text{ with }a+b>d. γ a p + b = 0 for all 0 ≤ a , b < p with a + b > d . Thus a nonzero ( x ) j (x)_j ( x ) j j < p 2 j<p^2 j < p 2 j j j p p p d d d
Proof. Put y = x p − x y=x^p-x y = x p − x H = Q + y T H=Q+yT H = Q + y T F p [ x ] \mathbb{F}_p[x] F p [ x ] U ↦ U p U\mapsto U^p U ↦ U p ( U + V ) p = U p + V p (U+V)^p=U^p+V^p ( U + V ) p = U p + V p p p p F p \mathbb{F}_p F p Q ( x ) p = Q ( x p ) Q(x)^p=Q(x^p) Q ( x ) p = Q ( x p ) H = Q + y T H=Q+yT H = Q + y T
H ( x ) p = Q ( x ) p + y p T ( x ) p = Q ( x p ) + y p T ( x ) p = Q ( x + y ) + y p T ( x ) p (14) H(x)^p=Q(x)^p+y^pT(x)^p=Q(x^p)+y^pT(x)^p=Q(x+y)+y^pT(x)^p \tag*{(14)} H ( x ) p = Q ( x ) p + y p T ( x ) p = Q ( x p ) + y p T ( x ) p = Q ( x + y ) + y p T ( x ) p (14) :::`
(since x p = x + y x^p=x+y x p = x + y ( x ) a p + b (x)_{ap+b} ( x ) a p + b 0 0 0 0 ≤ a , b < p 0 \le a,b < p 0 ≤ a , b < p a + b > d a+b>d a + b > d
For the second term, apply the coefficient-shift identity (13) with a = p a=p a = p P = T ( x ) p P=T(x)^p P = T ( x ) p
[ ( x ) i ] ( y p T ( x ) p ) = [ ( x ) i − p 2 ] ( T ( x ) p ) = 0 for all 0 ≤ i < p 2 . [(x)_i]\left(y^pT(x)^p\right)=[(x)_{i-p^2}]\left(T(x)^p\right)=0 \qquad\text{for all }0\le i<p^2. [( x ) i ] ( y p T ( x ) p ) = [( x ) i − p 2 ] ( T ( x ) p ) = 0 for all 0 ≤ i < p 2 . The last equality holds because i − p 2 < 0 i-p^2<0 i − p 2 < 0
It remains to examine Q ( x + y ) Q(x+y) Q ( x + y ) x x x y y y y = x p − x y=x^p-x y = x p − x deg Q ≤ d \deg Q\le d deg Q ≤ d x b y a x^b y^a x b y a a + b ≤ d a+b\le d a + b ≤ d x b x^b x b ( x ) t (x)_t ( x ) t 0 ≤ t ≤ b 0\le t\le b 0 ≤ t ≤ b y a y^a y a ( x ) a p + t (x)_{ap+t} ( x ) a p + t (11) . Thus, Q ( x + y ) Q(x+y) Q ( x + y ) F p \mathbb{F}_p F p ( x ) a p + t (x)_{ap+t} ( x ) a p + t a p + t ap+t a p + t
a , t ≥ 0 and a + t ≤ d . a,t\ge0 \quad\text{and}\quad a+t\le d. a , t ≥ 0 and a + t ≤ d . Since d < p d<p d < p a , t < p a,t<p a , t < p a a a t t t p p p
Lemma 2.3. Suppose P ∈ R [ x ] P\in R[x] P ∈ R [ x ]
∑ r = 0 p − 1 P ( r ) ∈ p R . (15) \sum_{r=0}^{p-1}P(r)\in pR. \tag*{(15)} r = 0 ∑ p − 1 P ( r ) ∈ pR . (15) Then
Δ k ( p − 1 ) ( P p ) ( 0 ) ∈ p k R for all 1 ≤ k ≤ p . \Delta^{k(p-1)}(P^p)(0)\in p^kR \qquad\text{for all }1\le k\le p. Δ k ( p − 1 ) ( P p ) ( 0 ) ∈ p k R for all 1 ≤ k ≤ p . Proof. Write P ( x ) p = ∑ j ≥ 0 c j ( x ) j P(x)^p=\sum_{j\ge0}c_j(x)_j P ( x ) p = ∑ j ≥ 0 c j ( x ) j c j ∈ R c_j\in R c j ∈ R m = k ( p − 1 ) m=k(p-1) m = k ( p − 1 ) 1 ≤ k ≤ p 1\le k\le p 1 ≤ k ≤ p m < p 2 m<p^2 m < p 2 (6) , we have
v p ( m ! ) = ⌊ m p ⌋ = k − 1. (16) v_p(m!)=\left\lfloor\frac{m}{p}\right\rfloor=k-1. \tag*{(16)} v p ( m !) = ⌊ p m ⌋ = k − 1. (16) (For the last equality, note that m / p = k − k / p m/p=k-k/p m / p = k − k / p 1 ≤ k ≤ p 1\le k\le p 1 ≤ k ≤ p 0 < k / p ≤ 1 0<k/p\le1 0 < k / p ≤ 1 k − 1 ≤ m / p < k k-1\le m/p<k k − 1 ≤ m / p < k ⌊ m / p ⌋ = k − 1 \lfloor m/p\rfloor=k-1 ⌊ m / p ⌋ = k − 1 (9) , the difference we want to study is
Δ m ( P p ) ( 0 ) = m ! c m . \Delta^m(P^p)(0)=m!c_m. Δ m ( P p ) ( 0 ) = m ! c m . We need this product to be divisible by p k p^k p k (16) says that m ! m! m ! k − 1 k-1 k − 1 p p p c m c_m c m c m ∈ p R c_m\in pR c m ∈ pR m = k ( p − 1 ) m=k(p-1) m = k ( p − 1 )
This is a question modulo p p p R R R p p p F p \mathbb{F}_p F p R / p R ≅ Z / p Z = F p R/pR\cong\mathbb{Z}/p\mathbb{Z}=\mathbb{F}_p R / pR ≅ Z / p Z = F p F p [ x ] \mathbb{F}_p[x] F p [ x ] F p \mathbb{F}_p F p p p p P ‾ \overline{P} P P P P p p p P ‾ p = ∑ j ≥ 0 c j ( x ) j \overline{P}^{p}=\sum_{j\ge0}c_j(x)_j P p = ∑ j ≥ 0 c j ( x ) j p p p P ‾ p = ∑ j ≥ 0 c j ‾ ( x ) j \overline{P}^{p}=\sum_{j\ge0}\overline{c_j}(x)_j P p = ∑ j ≥ 0 c j ( x ) j P ‾ p \overline{P}^{p} P p c j ‾ \overline{c_j} c j c j ‾ = [ ( x ) j ] ( P ‾ p ) \overline{c_j}=[(x)_j](\overline{P}^{p}) c j = [( x ) j ] ( P p ) j ≥ 0 j\ge0 j ≥ 0
We first replace P ‾ \overline{P} P p p p F p \mathbb{F}_p F p y = x p − x y=x^p-x y = x p − x P ‾ \overline{P} P y y y
P ‾ = Q + y T , where Q , T ∈ F p [ x ] with deg Q < p . \overline{P}=Q+yT,\qquad\text{where }Q,T\in\mathbb{F}_p[x]\text{ with }\deg Q<p. P = Q + y T , where Q , T ∈ F p [ x ] with deg Q < p . Fermat’s little theorem says that y ( r ) = 0 y(r)=0 y ( r ) = 0 r ∈ F p r\in\mathbb{F}_p r ∈ F p Q ( r ) = P ‾ ( r ) Q(r)=\overline{P}(r) Q ( r ) = P ( r ) r ∈ F p r\in\mathbb{F}_p r ∈ F p (15) rewrites as
∑ r ∈ F p Q ( r ) = 0. (17) \sum_{r\in\mathbb{F}_p}Q(r)=0. \tag*{(17)} r ∈ F p ∑ Q ( r ) = 0. (17) This forces the coefficient of x p − 1 x^{p-1} x p − 1 Q Q Q
∑ r ∈ F p r b = { 0 , if 0 ≤ b < p − 1 , − 1 , if b = p − 1 for every 0 ≤ b < p . (18) \sum_{r\in\mathbb{F}_p}r^b=
\begin{cases}
0, & \text{if }0\le b<p-1,\\
-1, & \text{if }b=p-1
\end{cases}
\qquad\text{for every }0\le b<p. \tag*{(18)} r ∈ F p ∑ r b = { 0 , − 1 , if 0 ≤ b < p − 1 , if b = p − 1 for every 0 ≤ b < p . (18) which we prove in Appendix § 9 . Applying (18) term by term to Q Q Q ∑ r ∈ F p Q ( r ) \sum_{r\in\mathbb{F}_p}Q(r) ∑ r ∈ F p Q ( r ) x p − 1 x^{p-1} x p − 1 Q Q Q deg Q < p \deg Q<p deg Q < p (17) tells us that the latter coefficient is 0. In other words,
deg Q ≤ p − 2. \deg Q\le p-2. deg Q ≤ p − 2. We can therefore apply Lemma 2.2 to H = P ‾ H=\overline{P} H = P d = p − 2 d=p-2 d = p − 2 [ ( x ) a p + b ] ( P ‾ p ) [(x)_{ap+b}](\overline{P}^{p}) [( x ) a p + b ] ( P p ) a p + b ap+b a p + b 0 ≤ a , b < p 0\le a,b<p 0 ≤ a , b < p a + b > p − 2 a+b>p-2 a + b > p − 2 k ( p − 1 ) k(p-1) k ( p − 1 ) 1 ≤ k ≤ p 1\le k\le p 1 ≤ k ≤ p
k ( p − 1 ) = a p + b for a = k − 1 and b = p − k . k(p-1)=ap+b\qquad\text{for }a=k-1\text{ and }b=p-k. k ( p − 1 ) = a p + b for a = k − 1 and b = p − k . (and these values a a a b b b 0 ≤ a < p 0\le a<p 0 ≤ a < p 0 ≤ b < p 0\le b<p 0 ≤ b < p a + b = ( k − 1 ) + ( p − k ) = p − 1 > p − 2 a+b=(k-1)+(p-k)=p-1>p-2 a + b = ( k − 1 ) + ( p − k ) = p − 1 > p − 2 [ ( x ) k ( p − 1 ) ] ( P ‾ p ) [(x)_{k(p-1)}](\overline{P}^{p}) [( x ) k ( p − 1 ) ] ( P p ) c k ( p − 1 ) ∈ p R c_{k(p-1)}\in pR c k ( p − 1 ) ∈ pR p p p
Remark 2.4. For example, when p = 5 p=5 p = 5 deg Q ≤ 3 \deg Q\le3 deg Q ≤ 3 P ‾ 5 \overline{P}^{5} P 5
0 , 1 , 2 , 3 , 5 , 6 , 7 , 10 , 11 , 15. 0,1,2,3,\quad5,6,7,\quad10,11,\quad15. 0 , 1 , 2 , 3 , 5 , 6 , 7 , 10 , 11 , 15. None is one of 4, 8, 12, 16, 20, the indices needed for the first five averaging depths. The factorials at these latter indices have respective 5-adic valuations 0, 1, 2, 3, 4; the lemma supplies one further factor of 5.
From local interpolation to arbitrary functions
Recall that our interest lies in functions f : Z → Q f:\mathbb{Z}\to\mathbb{Q} f : Z → Q m m m Δ m f \Delta^m f Δ m f m + 1 m+1 m + 1 f f f f f f
Δ m = ( E − id ) m = ∑ r = 0 m ( − 1 ) m − r ( m r ) E r \Delta^m=(E-\operatorname{id})^m=\sum_{r=0}^{m}(-1)^{m-r}\binom{m}{r}E^r Δ m = ( E − id ) m = r = 0 ∑ m ( − 1 ) m − r ( r m ) E r gives
Δ m f ( n ) = ∑ r = 0 m ( − 1 ) m − r ( m r ) f ( n + r ) . (19) \Delta^m f(n)=\sum_{r=0}^{m}(-1)^{m-r}\binom{m}{r}f(n+r). \tag*{(19)} Δ m f ( n ) = r = 0 ∑ m ( − 1 ) m − r ( r m ) f ( n + r ) . (19) This formula makes precise how an interval of agreement shrinks when we take differences. Suppose two functions f , g : Z → Q f,g:\mathbb{Z}\to\mathbb{Q} f , g : Z → Q [ a , b ] [a,b] [ a , b ] a ≤ b a\le b a ≤ b
Δ j f ( t ) = Δ j g ( t ) for all 0 ≤ j ≤ b − a and a ≤ t ≤ b − j . (20) \Delta^j f(t)=\Delta^j g(t)\qquad\text{for all }0\le j\le b-a\text{ and }a\le t\le b-j. \tag*{(20)} Δ j f ( t ) = Δ j g ( t ) for all 0 ≤ j ≤ b − a and a ≤ t ≤ b − j . (20) Indeed, the formula for Δ j f ( t ) \Delta^j f(t) Δ j f ( t ) t , t + 1 , … , t + j t,t+1,\ldots,t+j t , t + 1 , … , t + j [ a , b ] [a,b] [ a , b ] f f f g g g Δ \Delta Δ j j j Δ \Delta Δ j j j
In particular, suppose a polynomial P ∈ Q [ x ] P\in\mathbb{Q}[x] P ∈ Q [ x ] P ( r ) = f ( n + r ) P(r)=f(n+r) P ( r ) = f ( n + r ) 0 ≤ r ≤ m 0\le r\le m 0 ≤ r ≤ m n n n m ≥ 0 m\ge0 m ≥ 0 r ↦ P ( r ) r\mapsto P(r) r ↦ P ( r ) r ↦ f ( n + r ) r\mapsto f(n+r) r ↦ f ( n + r )
( Δ j P ) ( r ) = ( Δ j f ) ( n + r ) for all 0 ≤ j ≤ m and 0 ≤ r ≤ m − j . (21) (\Delta^jP)(r)=(\Delta^j f)(n+r)\qquad\text{for all }0\le j\le m\text{ and }0\le r\le m-j. \tag*{(21)} ( Δ j P ) ( r ) = ( Δ j f ) ( n + r ) for all 0 ≤ j ≤ m and 0 ≤ r ≤ m − j . (21) Here polynomial differences agree with differences of the evaluated function by (7) . For j = m j=m j = m r = 0 r=0 r = 0 Δ m P ( 0 ) = Δ m f ( n ) \Delta^mP(0)=\Delta^m f(n) Δ m P ( 0 ) = Δ m f ( n ) P p P^p P p f p f^p f p
Newton interpolation constructs the polynomial we need directly from these differences. Recall that for each j ≥ 0 j\ge0 j ≥ 0 ( x j ) = ( x ) j / j ! ∈ Q [ x ] \binom{x}{j}=(x)_j/j!\in\mathbb{Q}[x] ( j x ) = ( x ) j / j ! ∈ Q [ x ] 3 f : Z → Q f:\mathbb{Z}\to\mathbb{Q} f : Z → Q
P ( x ) = ∑ j = 0 m Δ j f ( n ) ( x j ) (22) P(x)=\sum_{j=0}^{m}\Delta^j f(n)\binom{x}{j} \tag*{(22)} P ( x ) = j = 0 ∑ m Δ j f ( n ) ( j x ) (22) (known as the m m m Newton interpolant of f f f n n n f ( n + x ) f(n+x) f ( n + x ) x = 0 , … , m x=0,\ldots,m x = 0 , … , m u = f ( n ) u=f(n) u = f ( n ) v = f ( n + 1 ) v=f(n+1) v = f ( n + 1 ) w = f ( n + 2 ) w=f(n+2) w = f ( n + 2 )
P ( x ) = u + ( v − u ) x + ( w − 2 v + u ) x ( x − 1 ) 2 . P(x)=u+(v-u)x+(w-2v+u)\frac{x(x-1)}{2}. P ( x ) = u + ( v − u ) x + ( w − 2 v + u ) 2 x ( x − 1 ) . Substitution of x = 0 , 1 , 2 x=0,1,2 x = 0 , 1 , 2 u , v , w u,v,w u , v , w
P ( r ) = f ( n + r ) for all 0 ≤ r ≤ m (23) P(r)=f(n+r)\qquad\text{for all }0\le r\le m \tag*{(23)} P ( r ) = f ( n + r ) for all 0 ≤ r ≤ m (23) is verified by the same binomial theorem we used for the operators: since E = id + Δ E=\operatorname{id}+\Delta E = id + Δ 0 ≤ r ≤ m 0\le r\le m 0 ≤ r ≤ m
f ( n + r ) = ( E r f ) ( n ) = ( ( id + Δ ) r f ) ( n ) = ∑ j = 0 r ( r j ) Δ j f ( n ) = P ( r ) f(n+r)=(E^r f)(n)=((\operatorname{id}+\Delta)^r f)(n)=\sum_{j=0}^{r}\binom{r}{j}\Delta^j f(n)=P(r) f ( n + r ) = ( E r f ) ( n ) = (( id + Δ ) r f ) ( n ) = j = 0 ∑ r ( j r ) Δ j f ( n ) = P ( r ) (here, all addends with j > r j>r j > r P ( r ) P(r) P ( r ) ( r j ) = 0 \binom{r}{j}=0 ( j r ) = 0 Lemma 1.4 .
Proof of Theorem 1.1 . The case ℓ = 0 \ell=0 ℓ = 0 f p f^p f p f f f 1 ≤ ℓ ≤ p 1\le\ell\le p 1 ≤ ℓ ≤ p q = p − 1 q=p-1 q = p − 1 Lemma 1.4 (equivalence of the first two conditions, applied to f p f^p f p f f f Δ k q ( f p ) ∈ p k Z \Delta^{kq}(f^p)\in p^k\mathbb{Z} Δ k q ( f p ) ∈ p k Z 0 ≤ k ≤ ℓ 0\le k\le\ell 0 ≤ k ≤ ℓ
p k ∣ Δ k q ( f p ) ( n ) for all n ∈ Z and 0 ≤ k ≤ ℓ . (24) p^k\mid\Delta^{kq}(f^p)(n)\qquad\text{for all }n\in\mathbb{Z}\text{ and }0\le k\le\ell. \tag*{(24)} p k ∣ Δ k q ( f p ) ( n ) for all n ∈ Z and 0 ≤ k ≤ ℓ . (24) Fix such n n n k k k m = k q m=kq m = k q m = k q ≤ ℓ q ≤ p q = p ( p − 1 ) < p 2 m=kq\le\ell q\le pq=p(p-1)<p^2 m = k q ≤ ℓ q ≤ pq = p ( p − 1 ) < p 2 k ≥ 1 k\ge1 k ≥ 1 k = 0 k=0 k = 0
P ( x ) = ∑ j = 0 m Δ j f ( n ) ( x j ) = ∑ j = 0 m Δ j f ( n ) j ! ( x ) j . (25) P(x)=\sum_{j=0}^{m}\Delta^j f(n)\binom{x}{j}=\sum_{j=0}^{m}\frac{\Delta^j f(n)}{j!}(x)_j. \tag*{(25)} P ( x ) = j = 0 ∑ m Δ j f ( n ) ( j x ) = j = 0 ∑ m j ! Δ j f ( n ) ( x ) j . (25) Newton interpolation – i.e., the formula (23) – gives
P ( r ) = f ( n + r ) for all 0 ≤ r ≤ m . (26) P(r)=f(n+r)\qquad\text{for all }0\le r\le m. \tag*{(26)} P ( r ) = f ( n + r ) for all 0 ≤ r ≤ m . (26) To apply Lemma 2.3 , we must check its two hypotheses. First, the coefficients of P P P R R R j ! j! j ! p p p Lemma 1.4 (this time applied to f f f j ≤ m j\le m j ≤ m Δ j f ∈ p ⌊ j / ( p − 1 ) ⌋ Z \Delta^j f\in p^{\lfloor j/(p-1)\rfloor}\mathbb{Z} Δ j f ∈ p ⌊ j / ( p − 1 )⌋ Z j ≤ m ≤ ℓ q j\le m\le\ell q j ≤ m ≤ ℓ q v p ( Δ j f ( n ) ) ≥ ⌊ j / ( p − 1 ) ⌋ v_p(\Delta^j f(n))\ge\lfloor j/(p-1)\rfloor v p ( Δ j f ( n )) ≥ ⌊ j / ( p − 1 )⌋ j ≤ m < p 2 j\le m<p^2 j ≤ m < p 2 (6) yields
v p ( j ! ) = ⌊ j p ⌋ ≤ ⌊ j p − 1 ⌋ . v_p(j!)=\left\lfloor\frac{j}{p}\right\rfloor\le\left\lfloor\frac{j}{p-1}\right\rfloor. v p ( j !) = ⌊ p j ⌋ ≤ ⌊ p − 1 j ⌋ . The numerator Δ j f ( n ) \Delta^j f(n) Δ j f ( n ) (25) therefore contains at least as many factors of p p p j ! j! j ! ( x ) j (x)_j ( x ) j R R R P ∈ R [ x ] P\in R[x] P ∈ R [ x ]
Second, the sum of P P P 0 , … , p − 1 0,\ldots,p-1 0 , … , p − 1 p R pR pR k ≥ 1 k\ge1 k ≥ 1 m = k q ≥ q = p − 1 m=kq\ge q=p-1 m = k q ≥ q = p − 1 r ∈ { 0 , 1 , … , p − 1 } r\in\{0,1,\ldots,p-1\} r ∈ { 0 , 1 , … , p − 1 } r ≤ m r\le m r ≤ m P ( r ) = f ( n + r ) P(r)=f(n+r) P ( r ) = f ( n + r ) (26) . Hence,
∑ r = 0 p − 1 P ( r ) = ∑ r = 0 p − 1 f ( n + r ) = p ( F p f ) ( n ) ∈ p Z \sum_{r=0}^{p-1}P(r)=\sum_{r=0}^{p-1}f(n+r)=p(F_p f)(n)\in p\mathbb{Z} r = 0 ∑ p − 1 P ( r ) = r = 0 ∑ p − 1 f ( n + r ) = p ( F p f ) ( n ) ∈ p Z (since 1 ≤ ℓ 1\le\ell 1 ≤ ℓ ℓ \ell ℓ f f f F p f F_p f F p f ( F p f ) ( n ) ∈ Z (F_p f)(n)\in\mathbb{Z} ( F p f ) ( n ) ∈ Z ∑ r = 0 p − 1 P ( r ) ∈ p Z ⊆ p R \sum_{r=0}^{p-1}P(r)\in p\mathbb{Z}\subseteq pR ∑ r = 0 p − 1 P ( r ) ∈ p Z ⊆ pR Lemma 2.3 consequently yields Δ k ( p − 1 ) ( P ) ( 0 ) ∈ p k R \Delta^{k(p-1)}(P)(0)\in p^kR Δ k ( p − 1 ) ( P ) ( 0 ) ∈ p k R m = k q = k ( p − 1 ) m=kq=k(p-1) m = k q = k ( p − 1 ) Δ m ( P p ) ( 0 ) ∈ p k R \Delta^m(P^p)(0)\in p^kR Δ m ( P p ) ( 0 ) ∈ p k R (21) (applied to P p P^p P p f p f^p f p m m m 0 0 0 P P P f f f j j j r r r Δ m ( P p ) ( 0 ) = Δ m ( f p ) ( n ) \Delta^m(P^p)(0)=\Delta^m(f^p)(n) Δ m ( P p ) ( 0 ) = Δ m ( f p ) ( n )
Δ m ( f p ) ( n ) = Δ m ( P p ) ( 0 ) ∈ p k R . \Delta^m(f^p)(n)=\Delta^m(P^p)(0)\in p^kR. Δ m ( f p ) ( n ) = Δ m ( P p ) ( 0 ) ∈ p k R . The left side is an integer, so it is therefore divisible by p k p^k p k p k ∣ Δ m ( f p ) ( n ) = Δ k q ( f p ) ( n ) p^k\mid\Delta^m(f^p)(n)=\Delta^{kq}(f^p)(n) p k ∣ Δ m ( f p ) ( n ) = Δ k q ( f p ) ( n ) m = k q m=kq m = k q (24) . As n n n k k k Lemma 1.4 proves that f p f^p f p ℓ \ell ℓ Theorem 1.1 is thus proved. □
Polynomials and repeated averaging
The finite-depth theorem is now proved. To study larger depths, it helps to answer a more specific question: which polynomials remain integer-valued after arbitrarily many averaging steps?
A monomial x t x^t x t p p p
d ( t ) = ⌊ t p − 1 ⌋ − v p ( t ! ) . d(t)=\left\lfloor\frac{t}{p-1}\right\rfloor-v_p(t!). d ( t ) = ⌊ p − 1 t ⌋ − v p ( t !) . There is a reason for this expression. The difference criterion (Lemma 1.4 ) asks for ⌊ t / ( p − 1 ) ⌋ \lfloor t/(p-1)\rfloor ⌊ t / ( p − 1 )⌋ p p p t t t t t t x t x^t x t t ! t! t ! d ( t ) d(t) d ( t ) [3 ] , and use it both for p = 2 , 3 p=2,3 p = 2 , 3 p > 3 p>3 p > 3
Lemma 4.1. For t ≥ 0 t\geq0 t ≥ 0
d ( t ) = ⌊ t p − 1 ⌋ − v p ( t ! ) . d(t)=\left\lfloor\frac{t}{p-1}\right\rfloor-v_p(t!). d ( t ) = ⌊ p − 1 t ⌋ − v p ( t !) . Then:
(a) We have d ( t ) ≥ 0 d(t)\geq0 d ( t ) ≥ 0 t ≥ 0 t\geq0 t ≥ 0
(b) We have d ( p t ) = d ( t ) d(pt)=d(t) d ( pt ) = d ( t ) t ≥ 0 t\geq0 t ≥ 0
(c) We have d ( t ) ≥ 1 d(t)\geq1 d ( t ) ≥ 1 t > 0 t>0 t > 0 p − 1 ∣ t p-1\mid t p − 1 ∣ t
(d) For any t ≥ 0 t\geq0 t ≥ 0 n ↦ p d ( t ) n t n\mapsto p^{d(t)}n^t n ↦ p d ( t ) n t
Proof. For t > 0 t>0 t > 0 (6) gives
v p ( t ! ) = ∑ i ≥ 1 ⌊ t p i ⌋ ≤ ∑ i ≥ 1 t p i = t p − 1 . v_p(t!)=\sum_{i\geq1}\left\lfloor\frac{t}{p^i}\right\rfloor\leq\sum_{i\geq1}\frac{t}{p^i}=\frac{t}{p-1}. v p ( t !) = i ≥ 1 ∑ ⌊ p i t ⌋ ≤ i ≥ 1 ∑ p i t = p − 1 t . This implies part (c) (since ⌊ t / ( p − 1 ) ⌋ = t / ( p − 1 ) \left\lfloor t/(p-1)\right\rfloor=t/(p-1) ⌊ t / ( p − 1 ) ⌋ = t / ( p − 1 ) p − 1 ∣ t p-1\mid t p − 1 ∣ t v p ( t ! ) v_p(t!) v p ( t !) v p ( t ! ) < t / ( p − 1 ) v_p(t!)<t/(p-1) v p ( t !) < t / ( p − 1 ) v p ( t ! ) ≤ ⌊ t / ( p − 1 ) ⌋ v_p(t!)\leq\lfloor t/(p-1)\rfloor v p ( t !) ≤ ⌊ t / ( p − 1 )⌋ d ( 0 ) = 0 d(0)=0 d ( 0 ) = 0 (6) yields
v p ( ( p t ) ! ) = t + v p ( t ! ) , ⌊ p t p − 1 ⌋ = t + t p − 1 = t + ⌊ t p − 1 ⌋ , v_p((pt)!)=t+v_p(t!),\qquad
\left\lfloor\frac{pt}{p-1}\right\rfloor=t+\frac{t}{p-1}=t+\left\lfloor\frac{t}{p-1}\right\rfloor, v p (( pt )!) = t + v p ( t !) , ⌊ p − 1 pt ⌋ = t + p − 1 t = t + ⌊ p − 1 t ⌋ , e n d s m i d = 1 {ends_mid=1} e n d s m i d = 1 and hence d ( p t ) = d ( t ) d(pt)=d(t) d ( pt ) = d ( t ) t ≥ 0 t \ge0 t ≥ 0
It remains to prove part (d). First, we shall work with the polynomials p d ( t ) x t p^{d(t)}x^t p d ( t ) x t t ≥ 0 t \ge0 t ≥ 0
Define an R R R M p M_p M p R [ x ] R[x] R [ x ]
M p = { ∑ t = 0 N c t x t : N ≥ 0 , c t ∈ p d ( t ) R for all 0 ≤ t ≤ N } . (27) M_p=\left\{\sum_{t=0}^{N}c_tx^t:N\ge0,\ c_t\in p^{d(t)}R\text{ for all }0\le t\le N\right\}. \tag*{(27)} M p = { t = 0 ∑ N c t x t : N ≥ 0 , c t ∈ p d ( t ) R for all 0 ≤ t ≤ N } . (27) In words, a polynomial belongs to M p M_p M p x t x^t x t t t t d ( t ) d(t) d ( t ) p p p M p M_p M p R R R p d ( t ) x t p^{d(t)}x^t p d ( t ) x t
We will prove that averaging (i.e., the operator F p F_p F p M p M_p M p F p ( p d ( t ) x t ) ∈ M p F_p(p^{d(t)}x^t)\in M_p F p ( p d ( t ) x t ) ∈ M p t ≥ 0 t\ge0 t ≥ 0
For t = 0 t=0 t = 0 t > 0 t>0 t > 0 F p F_p F p ( x + r ) t (x+r)^t ( x + r ) t
F p ( p d ( t ) x t ) = p d ( t ) p ∑ r = 0 p − 1 ( x + r ) t = p d ( t ) − 1 ∑ r = 0 p − 1 ∑ j = 0 t ( t j ) x j r t − j = ∑ j = 0 t p d ( t ) − 1 ( t j ) ( ∑ r = 0 p − 1 r t − j ) x j . \begin{aligned}
F_p(p^{d(t)}x^t)&=\frac{p^{d(t)}}{p}\sum_{r=0}^{p-1}(x+r)^t\\
&=p^{d(t)-1}\sum_{r=0}^{p-1}\sum_{j=0}^{t}\binom{t}{j}x^jr^{t-j}\\
&=\sum_{j=0}^{t}p^{d(t)-1}\binom{t}{j}\left(\sum_{r=0}^{p-1}r^{t-j}\right)x^j.
\end{aligned} F p ( p d ( t ) x t ) = p p d ( t ) r = 0 ∑ p − 1 ( x + r ) t = p d ( t ) − 1 r = 0 ∑ p − 1 j = 0 ∑ t ( j t ) x j r t − j = j = 0 ∑ t p d ( t ) − 1 ( j t ) ( r = 0 ∑ p − 1 r t − j ) x j . Write S u = ∑ r = 0 p − 1 r u S_u=\sum_{r=0}^{p-1}r^u S u = ∑ r = 0 p − 1 r u j = t j=t j = t S 0 = p S_0=p S 0 = p ( t t ) = 1 \binom{t}{t}=1 ( t t ) = 1 p d ( t ) x t p^{d(t)}x^t p d ( t ) x t
F p ( p d ( t ) x t ) = p d ( t ) x t + ∑ j = 0 t − 1 p d ( t ) − 1 ( t j ) S t − j x j . F_p(p^{d(t)}x^t)=p^{d(t)}x^t+\sum_{j=0}^{t-1}p^{d(t)-1}\binom{t}{j}S_{t-j}x^j. F p ( p d ( t ) x t ) = p d ( t ) x t + j = 0 ∑ t − 1 p d ( t ) − 1 ( j t ) S t − j x j . The leading term of this polynomial is p d ( t ) x t p^{d(t)}x^t p d ( t ) x t M p M_p M p j < t j<t j < t u = t − j > 0 u=t-j>0 u = t − j > 0 x j x^j x j F p ( p d ( t ) x t ) F_p(p^{d(t)}x^t) F p ( p d ( t ) x t )
C j = p d ( t ) − 1 ( t j ) S u . (28) C_j=p^{d(t)-1}\binom{t}{j}S_u. \tag*{(28)} C j = p d ( t ) − 1 ( j t ) S u . (28) We must show C j ∈ p d ( j ) R C_j\in p^{d(j)}R C j ∈ p d ( j ) R v p ( C j ) ≥ d ( j ) v_p(C_j)\ge d(j) v p ( C j ) ≥ d ( j )
First, the binomial coefficient accounts for the factorials in d d d t = j + u t=j+u t = j + u ( t j ) \binom{t}{j} ( j t )
v p ( ( t j ) ) = v p ( t ! ) − v p ( j ! ) − v p ( u ! ) . v_p\left(\binom{t}{j}\right)=v_p(t!)-v_p(j!)-v_p(u!). v p ( ( j t ) ) = v p ( t !) − v p ( j !) − v p ( u !) . Adding d ( t ) = ⌊ t p − 1 ⌋ − v p ( t ! ) d(t)=\left\lfloor\frac{t}{p-1}\right\rfloor-v_p(t!) d ( t ) = ⌊ p − 1 t ⌋ − v p ( t !) v p ( t ! ) v_p(t!) v p ( t !)
d ( t ) + v p ( ( t j ) ) = ⌊ t p − 1 ⌋ − v p ( j ! ) − v p ( u ! ) . d(t)+v_p\left(\binom{t}{j}\right)=\left\lfloor\frac{t}{p-1}\right\rfloor-v_p(j!)-v_p(u!). d ( t ) + v p ( ( j t ) ) = ⌊ p − 1 t ⌋ − v p ( j !) − v p ( u !) . Since t = j + u t=j+u t = j + u
⌊ t p − 1 ⌋ = ⌊ j + u p − 1 ⌋ ≥ ⌊ j p − 1 ⌋ + ⌊ u p − 1 ⌋ , \left\lfloor\frac{t}{p-1}\right\rfloor=\left\lfloor\frac{j+u}{p-1}\right\rfloor\ge\left\lfloor\frac{j}{p-1}\right\rfloor+\left\lfloor\frac{u}{p-1}\right\rfloor, ⌊ p − 1 t ⌋ = ⌊ p − 1 j + u ⌋ ≥ ⌊ p − 1 j ⌋ + ⌊ p − 1 u ⌋ , since all x , y ∈ R x,y\in\mathbb{R} x , y ∈ R ⌊ x + y ⌋ ≥ ⌊ x ⌋ + ⌊ y ⌋ \lfloor x+y\rfloor\ge\lfloor x\rfloor+\lfloor y\rfloor ⌊ x + y ⌋ ≥ ⌊ x ⌋ + ⌊ y ⌋ v p ( j ! ) + v p ( u ! ) v_p(j!)+v_p(u!) v p ( j !) + v p ( u !)
d ( t ) + v p ( t j ) ≥ d ( j ) + d ( u ) . (29) d(t)+v_p\binom{t}{j}\ge d(j)+d(u). \tag*{(29)} d ( t ) + v p ( j t ) ≥ d ( j ) + d ( u ) . (29) Second, we claim that
d ( u ) + v p ( S u ) ≥ 1. (30) d(u)+v_p(S_u)\ge1. \tag*{(30)} d ( u ) + v p ( S u ) ≥ 1. (30) Indeed, if p − 1 p-1 p − 1 u u u d ( u ) ≥ 1 d(u)\ge1 d ( u ) ≥ 1 Lemma 4.1 (c) (since u > 0 u>0 u > 0 (30) follows. If p − 1 p-1 p − 1 u u u S u S_u S u p p p (18) 4 v p ( S u ) ≥ 1 v_p(S_u)\ge1 v p ( S u ) ≥ 1 (30) follows again. In either case, (30) is proved.
Now, using (28) , (29) and (30) in sequence, we find
v p ( C j ) = d ( t ) − 1 + v p ( t j ) + v p ( S u ) ≥ d ( j ) + d ( u ) − 1 + v p ( S u ) ≥ d ( j ) , v_p(C_j)=d(t)-1+v_p\binom{t}{j}+v_p(S_u)\ge d(j)+d(u)-1+v_p(S_u)\ge d(j), v p ( C j ) = d ( t ) − 1 + v p ( j t ) + v p ( S u ) ≥ d ( j ) + d ( u ) − 1 + v p ( S u ) ≥ d ( j ) , so C j ∈ p d ( j ) R C_j\in p^{d(j)}R C j ∈ p d ( j ) R x j x^j x j F p ( p d ( t ) x t ) F_p(p^{d(t)}x^t) F p ( p d ( t ) x t ) p d ( j ) p^{d(j)} p d ( j ) R R R j j j F p ( p d ( t ) x t ) ∈ M p F_p(p^{d(t)}x^t)\in M_p F p ( p d ( t ) x t ) ∈ M p t ≥ 0 t\ge0 t ≥ 0 F p M p ⊆ M p F_pM_p\subseteq M_p F p M p ⊆ M p
Now, fix t ≥ 0 t\ge0 t ≥ 0 f : Z → Z f:\mathbb{Z}\to\mathbb{Z} f : Z → Z f ( n ) = p d ( t ) n t f(n)=p^{d(t)}n^t f ( n ) = p d ( t ) n t f f f F p k f F_p^k f F p k f k ≥ 0 k\ge0 k ≥ 0 p d ( t ) x t ∈ M p p^{d(t)}x^t\in M_p p d ( t ) x t ∈ M p F p M p ⊆ M p F_pM_p\subseteq M_p F p M p ⊆ M p k k k
F p k ( p d ( t ) x t ) ∈ M p ⊆ R [ x ] for every k ≥ 0. F_p^k(p^{d(t)}x^t)\in M_p\subseteq R[x]\qquad\text{for every }k\ge0. F p k ( p d ( t ) x t ) ∈ M p ⊆ R [ x ] for every k ≥ 0. Compatibility with evaluation, (7) , therefore gives
( F p k f ) ( n ) ∈ R for all k ≥ 0 and n ∈ Z (31) (F_p^k f)(n)\in R\qquad\text{for all }k\ge0\text{ and }n\in\mathbb{Z} \tag*{(31)} ( F p k f ) ( n ) ∈ R for all k ≥ 0 and n ∈ Z (31) (since f = ev ( p d ( t ) x t ) f=\operatorname{ev}(p^{d(t)}x^t) f = ev ( p d ( t ) x t ) F p k f = ev ( F p k ( p d ( t ) x t ) ) F_p^k f=\operatorname{ev}(F_p^k(p^{d(t)}x^t)) F p k f = ev ( F p k ( p d ( t ) x t )) f f f F p F_p F p p p p p p p p k ( F p k f ) ( n ) p^k(F_p^k f)(n) p k ( F p k f ) ( n ) ( F p k f ) ( n ) (F_p^k f)(n) ( F p k f ) ( n ) Z [ 1 / p ] \mathbb{Z}[1/p] Z [ 1/ p ] p p p (31) , we see that ( F p k f ) ( n ) ∈ R ∩ Z [ 1 / p ] = Z (F_p^k f)(n)\in R\cap\mathbb{Z}[1/p]=\mathbb{Z} ( F p k f ) ( n ) ∈ R ∩ Z [ 1/ p ] = Z Z [ 1 / p ] \mathbb{Z}[1/p] Z [ 1/ p ] p p p R R R p p p R ∩ Z [ 1 / p ] R\cap\mathbb{Z}[1/p] R ∩ Z [ 1/ p ] 1 1 1 ( F p k f ) ( n ) (F_p^k f)(n) ( F p k f ) ( n ) k ≥ 0 k\ge0 k ≥ 0 n ∈ Z n\in\mathbb{Z} n ∈ Z f f f
Let us next record the analogue of Lemma 1.4 for R R R p p p q = p − 1 q=p-1 q = p − 1
Lemma 4.2 (Difference criterion over R R R f : Z → Q f:\mathbb{Z}\to\mathbb{Q} f : Z → Q ℓ \ell ℓ
We have F p k f ∈ R Z F_p^k f\in R^{\mathbb{Z}} F p k f ∈ R Z 0 ≤ k ≤ ℓ 0\leq k\leq\ell 0 ≤ k ≤ ℓ
We have Δ k q f ∈ p k R Z \Delta^{kq}f\in p^kR^{\mathbb{Z}} Δ k q f ∈ p k R Z 0 ≤ k ≤ ℓ 0\leq k\leq\ell 0 ≤ k ≤ ℓ
We have Δ j f ∈ p ⌊ j / q ⌋ R Z \Delta^j f\in p^{\lfloor j/q\rfloor}R^{\mathbb{Z}} Δ j f ∈ p ⌊ j / q ⌋ R Z 0 ≤ j ≤ ℓ q 0\leq j\leq\ell q 0 ≤ j ≤ ℓ q
Proof. This is an analogue of Lemma 1.4 with some Z \mathbb{Z} Z R R R R R R R R R Q \mathbb{Q} Q
We can now describe all the polynomials P P P F p k P F_p^kP F p k P R R R R R R
M p = { ∑ t = 0 N c t x t : N ≥ 0 , c t ∈ p d ( t ) R for all 0 ≤ t ≤ N } (32) M_p=\left\{\sum_{t=0}^{N}c_tx^t:N\geq0,\ c_t\in p^{d(t)}R\text{ for all }0\leq t\leq N\right\} \tag*{(32)} M p = { t = 0 ∑ N c t x t : N ≥ 0 , c t ∈ p d ( t ) R for all 0 ≤ t ≤ N } (32) of R [ x ] R[x] R [ x ] Lemma 4.1 ).
We recall that each polynomial P ( x ) ∈ Q [ x ] P(x)\in\mathbb{Q}[x] P ( x ) ∈ Q [ x ] Q \mathbb{Q} Q ∑ j b j ( x ) j \sum_j b_j(x)_j ∑ j b j ( x ) j ( x ) j = j ! ( x j ) (x)_j=j!\binom{x}{j} ( x ) j = j ! ( j x ) ∑ j b j j ! ( x j ) \sum_j b_jj!\binom{x}{j} ∑ j b j j ! ( j x ) P ( x ) ∈ Q [ x ] P(x)\in\mathbb{Q}[x] P ( x ) ∈ Q [ x ] Q \mathbb{Q} Q ∑ j a j ( x j ) \sum_j a_j\binom{x}{j} ∑ j a j ( j x ) a j a_j a j
Proposition 4.3 (Polynomial criterion). For P ∈ Q [ x ] P\in\mathbb{Q}[x] P ∈ Q [ x ]
We have F p k P ( n ) ∈ R F_p^kP(n)\in R F p k P ( n ) ∈ R k ≥ 0 k\geq0 k ≥ 0 n ∈ Z n\in\mathbb{Z} n ∈ Z
Writing P ( x ) = ∑ j c j x j P(x)=\sum_jc_jx^j P ( x ) = ∑ j c j x j c j ∈ p d ( j ) R c_j\in p^{d(j)}R c j ∈ p d ( j ) R j j j P ∈ M p P\in M_p P ∈ M p
Writing P ( x ) = ∑ j b j ( x ) j P(x)=\sum_jb_j(x)_j P ( x ) = ∑ j b j ( x ) j b j ∈ p d ( j ) R b_j\in p^{d(j)}R b j ∈ p d ( j ) R j j j
Writing P ( x ) = ∑ j a j ( x j ) P(x)=\sum_ja_j\binom{x}{j} P ( x ) = ∑ j a j ( j x ) a j ∈ p ⌊ j / ( p − 1 ) ⌋ R a_j\in p^{\lfloor j/(p-1)\rfloor}R a j ∈ p ⌊ j / ( p − 1 )⌋ R j j j
We have Δ r ( p − 1 ) P ( n ) ∈ p r R \Delta^{r(p-1)}P(n)\in p^rR Δ r ( p − 1 ) P ( n ) ∈ p r R n ∈ Z n\in\mathbb{Z} n ∈ Z r ≥ 0 r\geq0 r ≥ 0
We have Δ j P ( n ) ∈ p ⌊ j / ( p − 1 ) ⌋ R \Delta^jP(n)\in p^{\lfloor j/(p-1)\rfloor}R Δ j P ( n ) ∈ p ⌊ j / ( p − 1 )⌋ R n ∈ Z n\in\mathbb{Z} n ∈ Z j ≥ 0 j\geq0 j ≥ 0
If P P P Z \mathbb{Z} Z n ↦ P ( n ) n\mapsto P(n) n ↦ P ( n )
Proof. We first compare the conditions involving values and differences. Put f ( n ) = P ( n ) f(n)=P(n) f ( n ) = P ( n ) n ∈ Z n\in\mathbb{Z} n ∈ Z f f f (7) . Allowing ℓ \ell ℓ ( 1 ) ⇔ ( 5 ) ⇔ ( 6 ) (1)\Leftrightarrow(5)\Leftrightarrow(6) ( 1 ) ⇔ ( 5 ) ⇔ ( 6 )
Next we prove ( 6 ) ⇒ ( 4 ) ⇒ ( 5 ) (6)\Rightarrow(4)\Rightarrow(5) ( 6 ) ⇒ ( 4 ) ⇒ ( 5 ) ( x j ) = ( x ) j / j ! \binom{x}{j}=(x)_j/j! ( j x ) = ( x ) j / j ! P = ∑ j a j ( x j ) P=\sum_j a_j\binom{x}{j} P = ∑ j a j ( j x )
P = ∑ j a j j ! ( x ) j . P=\sum_j\frac{a_j}{j!}(x)_j. P = j ∑ j ! a j ( x ) j . Thus (9) gives Δ j P ( 0 ) = j ! ( a j / j ! ) = a j \Delta^jP(0)=j!(a_j/j!)=a_j Δ j P ( 0 ) = j ! ( a j / j !) = a j n = 0 n=0 n = 0 a j ∈ p ⌊ j / ( p − 1 ) ⌋ R a_j\in p^{\lfloor j/(p-1)\rfloor}R a j ∈ p ⌊ j / ( p − 1 )⌋ R
To prove ( 4 ) ⇒ ( 5 ) (4)\Rightarrow(5) ( 4 ) ⇒ ( 5 ) (8) by j ! j! j !
Δ ( x j ) = ( x j − 1 ) for all j ≥ 1 , Δ ( x 0 ) = 0. \Delta\binom{x}{j}=\binom{x}{j-1}\quad\text{for all }j\geq1,\qquad\Delta\binom{x}{0}=0. Δ ( j x ) = ( j − 1 x ) for all j ≥ 1 , Δ ( 0 x ) = 0. So each iteration of Δ \Delta Δ ( x j ) \binom{x}{j} ( j x ) j j j Δ k ( x j ) = ( x j − k ) \Delta^k\binom{x}{j}=\binom{x}{j-k} Δ k ( j x ) = ( j − k x ) j , k ≥ 0 j,k\geq0 j , k ≥ 0 0 0 0 j − k < 0 j-k<0 j − k < 0 r ≥ 0 r\geq0 r ≥ 0
Δ r ( p − 1 ) P ( x ) = ∑ j ≥ r ( p − 1 ) a j ( x j − r ( p − 1 ) ) . (33) \Delta^{r(p-1)}P(x)=\sum_{j\geq r(p-1)}a_j\binom{x}{j-r(p-1)}. \tag*{(33)} Δ r ( p − 1 ) P ( x ) = j ≥ r ( p − 1 ) ∑ a j ( j − r ( p − 1 ) x ) . (33) For each index in this sum, j ≥ r ( p − 1 ) j\geq r(p-1) j ≥ r ( p − 1 ) ⌊ j / ( p − 1 ) ⌋ ≥ r \lfloor j/(p-1)\rfloor\geq r ⌊ j / ( p − 1 )⌋ ≥ r a j ∈ p r R a_j\in p^rR a j ∈ p r R ( x k ) \binom{x}{k} ( k x ) Z \mathbb{Z} Z (33) shows that Δ r ( p − 1 ) P \Delta^{r(p-1)}P Δ r ( p − 1 ) P p r R p^rR p r R r r r
The equivalence of (3) and (4) is also easy, since the respective coefficients are related by a j = j ! b j a_j=j!b_j a j = j ! b j ( x ) j = j ! ( x j ) (x)_j=j!\binom{x}{j} ( x ) j = j ! ( j x ) a j ∈ p ⌊ j / ( p − 1 ) ⌋ R a_j\in p^{\lfloor j/(p-1)\rfloor}R a j ∈ p ⌊ j / ( p − 1 )⌋ R b j ∈ p d ( j ) R b_j\in p^{d(j)}R b j ∈ p d ( j ) R
Next we prove ( 2 ) ⇒ ( 1 ) (2)\Rightarrow(1) ( 2 ) ⇒ ( 1 )
P ( x ) = ∑ j = 0 N u j p d ( j ) x j , with u j ∈ R . P(x)=\sum_{j=0}^{N}u_jp^{d(j)}x^j,\qquad\text{with }u_j\in R. P ( x ) = j = 0 ∑ N u j p d ( j ) x j , with u j ∈ R . For each j j j f j ( n ) = p d ( j ) n j f_j(n)=p^{d(j)}n^j f j ( n ) = p d ( j ) n j f j f_j f j F p k f j F_p^kf_j F p k f j k ≥ 0 k\geq0 k ≥ 0 ev P = ∑ j = 0 N u j f j \operatorname{ev}P=\sum_{j=0}^{N}u_jf_j ev P = ∑ j = 0 N u j f j F p k F_p^k F p k Q \mathbb{Q} Q (7) ),
( F p k P ) ( n ) = ∑ j = 0 N u j ⏟ ∈ R ( F p k f j ) ( n ) ⏟ ∈ Z ∈ R for all k ≥ 0 and n ∈ Z . (F_p^kP)(n)=\sum_{j=0}^{N}\underbrace{u_j}_{\in R}\underbrace{(F_p^kf_j)(n)}_{\in\mathbb{Z}}\in R\qquad\text{for all }k\geq0\text{ and }n\in\mathbb{Z}. ( F p k P ) ( n ) = j = 0 ∑ N ∈ R u j ∈ Z ( F p k f j ) ( n ) ∈ R for all k ≥ 0 and n ∈ Z . This is condition (1).
For the converse, we take a bird’s-eye view. Do not fix P P P M p M_p M p P ∈ Q [ x ] P\in\mathbb{Q}[x] P ∈ Q [ x ] M p ′ M'_p M p ′ P ∈ Q [ x ] P\in\mathbb{Q}[x] P ∈ Q [ x ] M p M_p M p M p ′ M'_p M p ′ R R R Q [ x ] \mathbb{Q}[x] Q [ x ] F p k F_p^k F p k R R R ( 2 ) ⇒ ( 1 ) (2)\Rightarrow(1) ( 2 ) ⇒ ( 1 ) M p ⊆ M p ′ M_p\subseteq M'_p M p ⊆ M p ′ M p ′ ⊆ M p M'_p\subseteq M_p M p ′ ⊆ M p P ∈ M p ′ P \in M'_p P ∈ M p ′ P ∈ M p P \in M_p P ∈ M p deg P \deg P deg P P = 0 P=0 P = 0 P ≠ 0 P \ne0 P = 0 c t x t c_t x^t c t x t P P P P ∈ M p ′ P \in M'_p P ∈ M p ′ j = t j=t j = t n = 0 n=0 n = 0
Δ t P ( 0 ) ∈ p ⌊ t / ( p − 1 ) ⌋ R . \Delta^t P(0) \in p^{\lfloor t/(p-1)\rfloor}R. Δ t P ( 0 ) ∈ p ⌊ t / ( p − 1 )⌋ R . Since ( x ) t (x)_t ( x ) t t t t P − c t ( x ) t P-c_t(x)_t P − c t ( x ) t t t t ( x ) 0 (x)_0 ( x ) 0 ( x ) 1 (x)_1 ( x ) 1 … \ldots … ( x ) t − 1 (x)_{t-1} ( x ) t − 1 ( x ) t (x)_t ( x ) t P P P c t c_t c t (9) gives Δ t P ( 0 ) = t ! c t \Delta^tP(0)=t!c_t Δ t P ( 0 ) = t ! c t
t ! c t = Δ t P ( 0 ) ∈ p ⌊ t / ( p − 1 ) ⌋ R , hence c t ∈ p d ( t ) R . t!c_t=\Delta^tP(0)\in p^{\lfloor t/(p-1)\rfloor}R,\qquad\text{hence}\qquad c_t\in p^{d(t)}R. t ! c t = Δ t P ( 0 ) ∈ p ⌊ t / ( p − 1 )⌋ R , hence c t ∈ p d ( t ) R . Therefore, c t x t ∈ M p ⊆ M p ′ c_tx^t\in M_p\subseteq M'_p c t x t ∈ M p ⊆ M p ′ P − c t x t ∈ M p ′ P-c_tx^t\in M'_p P − c t x t ∈ M p ′ P P P c t x t c_tx^t c t x t M p ′ M'_p M p ′ M p ′ M'_p M p ′ R R R P − c t x t ∈ M p P-c_tx^t\in M_p P − c t x t ∈ M p P − c t x t P-c_tx^t P − c t x t P P P c t x t ∈ M p c_tx^t\in M_p c t x t ∈ M p P ∈ M p P\in M_p P ∈ M p M p M_p M p R R R M p ′ ⊆ M p M'_p\subseteq M_p M p ′ ⊆ M p
Finally, suppose P P P f f f k ≥ 0 k\geq0 k ≥ 0 n ∈ Z n\in\mathbb{Z} n ∈ Z p k ( F p k f ) ( n ) p^k(F_p^k f)(n) p k ( F p k f ) ( n ) ( F p k f ) ( n ) (F_p^k f)(n) ( F p k f ) ( n ) p p p ( F p k f ) ( n ) (F_p^k f)(n) ( F p k f ) ( n ) R R R f f f f f f ( F p k f ) ( n ) ∈ Z ⊆ R (F_p^k f)(n)\in\mathbb{Z}\subseteq R ( F p k f ) ( n ) ∈ Z ⊆ R k , n k,n k , n
For example, when p = 3 p=3 p = 3 d ( 0 ) = d ( 1 ) = 0 d(0)=d(1)=0 d ( 0 ) = d ( 1 ) = 0 d ( 2 ) = 1 d(2)=1 d ( 2 ) = 1 d ( 3 ) = 0 d(3)=0 d ( 3 ) = 0 R [ x ] R[x] R [ x ] R R R x 2 x^2 x 2 x x x 3 x 2 3x^2 3 x 2 x 3 x^3 x 3 Z \mathbb{Z} Z x 2 x^2 x 2
F 3 ( x 2 ) = x 2 + 2 x + 5 3 . F_3(x^2)=x^2+2x+\frac{5}{3}. F 3 ( x 2 ) = x 2 + 2 x + 3 5 . This example illustrates why the coefficient conditions are useful: we can decide about all averaging stages without calculating them.
The criterion also lets us return to arbitrary functions without losing control at large depths. Although we match the function only on a finite interval, the interpolating polynomial will have integral averages at every depth. This useful fact is the content of the following lemma.
Lemma 4.4 (Local lifting). Let f ∈ Q Z f\in\mathbb{Q}^{\mathbb{Z}} f ∈ Q Z ℓ \ell ℓ n ∈ Z n\in\mathbb{Z} n ∈ Z m = ℓ ( p − 1 ) m=\ell(p-1) m = ℓ ( p − 1 ) P ∈ M p P\in M_p P ∈ M p
P ( r ) = f ( n + r ) for all 0 ≤ r ≤ m . P(r)=f(n+r)\qquad\text{for all }0\leq r\leq m. P ( r ) = f ( n + r ) for all 0 ≤ r ≤ m . In fact, the Newton interpolant
P ( x ) = ∑ j = 0 m Δ j f ( n ) ( x j ) (34) P(x)=\sum_{j=0}^{m}\Delta^j f(n)\binom{x}{j} \tag*{(34)} P ( x ) = j = 0 ∑ m Δ j f ( n ) ( j x ) (34) has these properties, and the function r ↦ P ( r ) r\mapsto P(r) r ↦ P ( r )
Proof. Define P P P (34) . The matching values P ( r ) = f ( n + r ) P(r)=f(n+r) P ( r ) = f ( n + r ) (23) . Also, each coefficient Δ j f ( n ) \Delta^j f(n) Δ j f ( n ) f f f ( x j ) \binom{x}{j} ( j x ) Z \mathbb{Z} Z P P P Z \mathbb{Z} Z f f f
For each j ≤ m j\leq m j ≤ m Δ j f ∈ p ⌊ j / ( p − 1 ) ⌋ Z R \Delta^j f\in p^{\lfloor j/(p-1)\rfloor}\mathbb{Z}R Δ j f ∈ p ⌊ j / ( p − 1 )⌋ Z R Δ j f ( n ) \Delta^j f(n) Δ j f ( n ) p ⌊ j / ( p − 1 ) ⌋ p^{\lfloor j/(p-1)\rfloor} p ⌊ j / ( p − 1 )⌋ Δ j f ( n ) ∈ p ⌊ j / ( p − 1 ) ⌋ R \Delta^j f(n)\in p^{\lfloor j/(p-1)\rfloor}R Δ j f ( n ) ∈ p ⌊ j / ( p − 1 )⌋ R (34) . Thus, the integer-valued polynomial P ∈ Q [ x ] P\in\mathbb{Q}[x] P ∈ Q [ x ] a j = Δ j f ( n ) a_j=\Delta^j f(n) a j = Δ j f ( n ) j ≤ m j\leq m j ≤ m a j = 0 a_j=0 a j = 0 j > m j>m j > m P ∈ M p P\in M_p P ∈ M p r ↦ P ( r ) r\mapsto P(r) r ↦ P ( r )
Every depth for p = 2 p=2 p = 2 p = 3 p=3 p = 3
We now have the ingredients to prove Theorem 1.2. The key distinction between p = 2 p=2 p = 2 p = 3 p=3 p = 3
Proof of Theorem 1.2. We first work with polynomials. Proposition 4.3 reduces the question to coefficient divisibility: we must show that M 2 M_2 M 2 M 3 M_3 M 3
For p = 2 p=2 p = 2 d d d d ( j ) = j − v 2 ( j ! ) d(j)=j-v_2(j!) d ( j ) = j − v 2 ( j !)
d ( i + j ) = d ( i ) + d ( j ) − v 2 ( ( i + j i ) ) ≤ d ( i ) + d ( j ) for all i , j ≥ 0. d(i+j)=d(i)+d(j)-v_2\left(\binom{i+j}{i}\right)\leq d(i)+d(j)\qquad\text{for all }i,j\geq0. d ( i + j ) = d ( i ) + d ( j ) − v 2 ( ( i i + j ) ) ≤ d ( i ) + d ( j ) for all i , j ≥ 0. The product of the two basic polynomials 2 d ( i ) x i 2^{d(i)}x^i 2 d ( i ) x i 2 d ( j ) x j 2^{d(j)}x^j 2 d ( j ) x j 2 d ( i ) + d ( j ) 2^{d(i)+d(j)} 2 d ( i ) + d ( j ) i + j i+j i + j d ( i + j ) d(i+j) d ( i + j ) 2 2 2 M 2 M_2 M 2 P = ∑ i a i 2 d ( i ) x i P=\sum_i a_i2^{d(i)}x^i P = ∑ i a i 2 d ( i ) x i Q = ∑ j b j 2 d ( j ) x j Q=\sum_j b_j2^{d(j)}x^j Q = ∑ j b j 2 d ( j ) x j a i , b j ∈ R a_i,b_j\in R a i , b j ∈ R
P Q = ∑ i , j a i b j ( 2 d ( i ) x i ) ( 2 d ( j ) x j ) . PQ=\sum_{i,j}a_i b_j\left(2^{d(i)}x^i\right)\left(2^{d(j)}x^j\right). P Q = i , j ∑ a i b j ( 2 d ( i ) x i ) ( 2 d ( j ) x j ) . Each product in parentheses belongs to M 2 M_2 M 2 M 2 M_2 M 2 R R R P Q ∈ M 2 PQ\in M_2 P Q ∈ M 2 1 1 1 M 2 M_2 M 2 d ( 0 ) = 0 d(0)=0 d ( 0 ) = 0 M 2 M_2 M 2 Q [ x ] \mathbb{Q}[x] Q [ x ]
For p = 3 p=3 p = 3 M 3 M_3 M 3 3 3 3
Here we have d ( j ) = ⌊ j / 2 ⌋ − v 3 ( j ! ) d(j)=\lfloor j/2\rfloor-v_3(j!) d ( j ) = ⌊ j /2 ⌋ − v 3 ( j !) i , j , k ≥ 0 i,j,k\geq0 i , j , k ≥ 0
d ( i + j + k ) − d ( i ) − d ( j ) − d ( k ) = ⌊ i + j + k 2 ⌋ − ⌊ i 2 ⌋ − ⌊ j 2 ⌋ − ⌊ k 2 ⌋ − v 3 ( ( i + j + k i , j , k ) ) . d(i+j+k)-d(i)-d(j)-d(k)=\left\lfloor\frac{i+j+k}{2}\right\rfloor-\left\lfloor\frac{i}{2}\right\rfloor-\left\lfloor\frac{j}{2}\right\rfloor-\left\lfloor\frac{k}{2}\right\rfloor-v_3\left(\binom{i+j+k}{i,j,k}\right). d ( i + j + k ) − d ( i ) − d ( j ) − d ( k ) = ⌊ 2 i + j + k ⌋ − ⌊ 2 i ⌋ − ⌊ 2 j ⌋ − ⌊ 2 k ⌋ − v 3 ( ( i , j , k i + j + k ) ) . Here the multinomial coefficient is an integer, and the difference of floors is at most 1. Indeed, write i = 2 a + ϵ i=2a+\epsilon i = 2 a + ϵ j = 2 b + η j=2b+\eta j = 2 b + η k = 2 c + θ k=2c+\theta k = 2 c + θ ϵ , η , θ \epsilon,\eta,\theta ϵ , η , θ ⌊ ( ϵ + η + θ ) / 2 ⌋ ≤ 1 \lfloor(\epsilon+\eta+\theta)/2\rfloor\le1 ⌊( ϵ + η + θ ) /2 ⌋ ≤ 1 v 3 ( ( i + j + k i , j , k ) ) ≥ 0 v_3\left(\binom{i+j+k}{i,j,k}\right) \ge0 v 3 ( ( i , j , k i + j + k ) ) ≥ 0
d ( i + j + k ) ≤ d ( i ) + d ( j ) + d ( k ) + 1 for all i , j , k ≥ 0. (35) d(i+j+k) \le d(i)+d(j)+d(k)+1 \qquad\text{for all } i,j,k \ge0. \tag*{(35)} d ( i + j + k ) ≤ d ( i ) + d ( j ) + d ( k ) + 1 for all i , j , k ≥ 0. (35) Write P = ∑ j c j x j ∈ M 3 P=\sum_j c_jx^j\in M_3 P = ∑ j c j x j ∈ M 3 v 3 ( c j ) ≥ d ( j ) v_3(c_j)\ge d(j) v 3 ( c j ) ≥ d ( j ) j j j P P P P 3 = ∑ i , j , k c i c j c k x i + j + k P^3=\sum_{i,j,k}c_ic_jc_kx^{i+j+k} P 3 = ∑ i , j , k c i c j c k x i + j + k
P 3 = ∑ j c j 3 x 3 j + 3 ∑ i ≠ j c i 2 c j x 2 i + j + 6 ∑ i < j < k c i c j c k x i + j + k . P^3=\sum_j c_j^3x^{3j}+3\sum_{i\ne j}c_i^2c_jx^{2i+j}+6\sum_{i<j<k}c_ic_jc_kx^{i+j+k}. P 3 = j ∑ c j 3 x 3 j + 3 i = j ∑ c i 2 c j x 2 i + j + 6 i < j < k ∑ c i c j c k x i + j + k . All sums are finite. First consider the pure terms c j 3 x 3 j c_j^3x^{3j} c j 3 x 3 j v 3 ( c j 3 ) = 3 v 3 ( c j ) v_3(c_j^3)=3v_3(c_j) v 3 ( c j 3 ) = 3 v 3 ( c j ) 3 d ( j ) 3d(j) 3 d ( j ) v 3 ( c j ) ≥ d ( j ) v_3(c_j)\ge d(j) v 3 ( c j ) ≥ d ( j ) M 3 M_3 M 3 d ( 3 j ) = d ( j ) d(3j)=d(j) d ( 3 j ) = d ( j ) Lemma 4.1 (b). Since d ( j ) ≥ 0 d(j)\ge0 d ( j ) ≥ 0 3 d ( j ) ≥ d ( j ) 3d(j)\ge d(j) 3 d ( j ) ≥ d ( j ) M 3 M_3 M 3
Each mixed term is 3 c i 2 c j x 2 i + j 3c_i^2c_jx^{2i+j} 3 c i 2 c j x 2 i + j i ≠ j i\ne j i = j 6 c i c j c k x i + j + k 6c_ic_jc_kx^{i+j+k} 6 c i c j c k x i + j + k i < j < k i<j<k i < j < k 1 + 2 d ( i ) + d ( j ) ≥ d ( 2 i + j ) 1+2d(i)+d(j)\ge d(2i+j) 1 + 2 d ( i ) + d ( j ) ≥ d ( 2 i + j ) (35) with indices i , i , j i,i,j i , i , j 1 + d ( i ) + d ( j ) + d ( k ) ≥ d ( i + j + k ) 1+d(i)+d(j)+d(k)\ge d(i+j+k) 1 + d ( i ) + d ( j ) + d ( k ) ≥ d ( i + j + k ) (35) . Thus every mixed term also belongs to M 3 M_3 M 3 P 3 ∈ M 3 P^3\in M_3 P 3 ∈ M 3
We now transfer these polynomial statements to functions. Fix a depth ℓ \ell ℓ n n n p = 2 p=2 p = 2 f , g ∈ Q Z f,g\in\mathbb{Q}^{\mathbb{Z}} f , g ∈ Q Z ℓ \ell ℓ Lemma 4.4 (applied here with m = ℓ m=\ell m = ℓ p − 1 = 1 p-1=1 p − 1 = 1 P , Q ∈ M 2 P,Q\in M_2 P , Q ∈ M 2
P ( s ) = f ( n + s ) , Q ( s ) = g ( n + s ) for all 0 ≤ s ≤ ℓ . (36) P(s)=f(n+s),\qquad Q(s)=g(n+s)\qquad\text{for all }0\le s\le\ell. \tag*{(36)} P ( s ) = f ( n + s ) , Q ( s ) = g ( n + s ) for all 0 ≤ s ≤ ℓ . (36) Their product P Q PQ P Q M 2 M_2 M 2 M 2 M_2 M 2 h ( s ) = P ( s ) Q ( s ) h(s)=P(s)Q(s) h ( s ) = P ( s ) Q ( s ) s ∈ Z s\in\mathbb{Z} s ∈ Z Proposition 4.3 (specifically, its last sentence) gives F 2 r h ∈ Z Z F_2^rh\in\mathbb{Z}^{\mathbb{Z}} F 2 r h ∈ Z Z r ≥ 0 r\ge0 r ≥ 0 (36) shows that
h ( s ) = ( f g ) ( n + s ) for all 0 ≤ s ≤ ℓ . (37) h(s)=(fg)(n+s)\qquad\text{for all }0\le s\le\ell. \tag*{(37)} h ( s ) = ( f g ) ( n + s ) for all 0 ≤ s ≤ ℓ . (37) Consider an arbitrary function w : Z → Q w:\mathbb{Z}\to\mathbb{Q} w : Z → Q F p r w F_p^rw F p r w r ( p − 1 ) + 1 r(p-1)+1 r ( p − 1 ) + 1 w w w F p F_p F p r ≥ 0 r\ge0 r ≥ 0 (1) gives
F p r = 1 p r ( id + E + ⋯ + E p − 1 ) r = 1 p r ∑ a 1 , … , a r ∈ { 0 , … , p − 1 } E a 1 + ⋯ + a r F_p^r=\frac{1}{p^r}(\operatorname{id}+E+\cdots+E^{p-1})^r
=\frac{1}{p^r}\sum_{\substack{a_1,\ldots,a_r\in\{0,\ldots,p-1\}}}E^{a_1+\cdots+a_r} F p r = p r 1 ( id + E + ⋯ + E p − 1 ) r = p r 1 a 1 , … , a r ∈ { 0 , … , p − 1 } ∑ E a 1 + ⋯ + a r by distributivity (where for r = 0 r=0 r = 0 E 0 E^0 E 0 a i a_i a i i i i w w w n n n
( F p r w ) ( n ) = 1 p r ∑ a 1 , … , a r ∈ { 0 , 1 , … , p − 1 } w ( n + a 1 + ⋯ + a r ) . (38) (F_p^rw)(n)=\frac{1}{p^r}\sum_{\substack{a_1,\ldots,a_r\in\{0,1,\ldots,p-1\}}}w(n+a_1+\cdots+a_r). \tag*{(38)} ( F p r w ) ( n ) = p r 1 a 1 , … , a r ∈ { 0 , 1 , … , p − 1 } ∑ w ( n + a 1 + ⋯ + a r ) . (38) for all r ≥ 0 r \ge0 r ≥ 0 p = 2 p=2 p = 2 a 1 + ⋯ + a r a_1+\cdots+a_r a 1 + ⋯ + a r 0 0 0 r r r 0 ≤ r ≤ ℓ 0 \le r \le\ell 0 ≤ r ≤ ℓ ( F 2 r ( f g ) ) ( n ) (F_2^r(fg))(n) ( F 2 r ( f g )) ( n ) ( F 2 r h ) ( 0 ) (F_2^r h)(0) ( F 2 r h ) ( 0 ) (38) , then each summand in the formula for ( F 2 r ( f g ) ) ( n ) (F_2^r(fg))(n) ( F 2 r ( f g )) ( n ) ( F 2 r h ) ( 0 ) (F_2^r h)(0) ( F 2 r h ) ( 0 ) (37) . Consequently,
( F 2 r ( f g ) ) ( n ) = ( F 2 r h ) ( 0 ) ∈ Z ( since F 2 r h ∈ Z Z ) . (F_2^r(fg))(n)=(F_2^r h)(0)\in\mathbb{Z}\qquad(\text{since }F_2^r h\in\mathbb{Z}^{\mathbb{Z}}). ( F 2 r ( f g )) ( n ) = ( F 2 r h ) ( 0 ) ∈ Z ( since F 2 r h ∈ Z Z ) . Since n n n F 2 r ( f g ) ∈ Z Z F_2^r(fg)\in\mathbb{Z}^{\mathbb{Z}} F 2 r ( f g ) ∈ Z Z r ≤ ℓ r\le\ell r ≤ ℓ f g fg f g ℓ \ell ℓ ℓ \ell ℓ F 2 F_2 F 2 1 1 1 ℓ \ell ℓ F 2 F_2 F 2 ℓ \ell ℓ p = 2 p=2 p = 2
For p = 3 p=3 p = 3 ℓ \ell ℓ f ∈ Q Z f\in\mathbb{Q}^{\mathbb{Z}} f ∈ Q Z P ∈ M 3 P\in M_3 P ∈ M 3
P ( s ) = f ( n + s ) for all 0 ≤ s ≤ 2 ℓ . (39) P(s)=f(n+s)\qquad\text{for all }0\le s\le2\ell. \tag*{(39)} P ( s ) = f ( n + s ) for all 0 ≤ s ≤ 2 ℓ . (39) (Such a P P P Lemma 4.4 .) As we saw above, P ∈ M 3 P\in M_3 P ∈ M 3 P 3 ∈ M 3 P^3\in M_3 P 3 ∈ M 3 h ( s ) = P ( s ) 3 h(s)=P(s)^3 h ( s ) = P ( s ) 3 P 3 P^3 P 3 M 3 M_3 M 3 Proposition 4.3 (again, its last sentence, applied to P 3 P^3 P 3 h h h F 3 r h ∈ Z Z F_3^r h\in\mathbb{Z}^{\mathbb{Z}} F 3 r h ∈ Z Z r ≥ 0 r\ge0 r ≥ 0 0 ≤ r ≤ ℓ 0\le r\le\ell 0 ≤ r ≤ ℓ a 1 + ⋯ + a r a_1+\cdots+a_r a 1 + ⋯ + a r (38) lies between 0 0 0 2 r ≤ 2 ℓ 2r\le2\ell 2 r ≤ 2 ℓ h ( s ) = P ( s ) 3 = f ( n + s ) 3 h(s)=P(s)^3=f(n+s)^3 h ( s ) = P ( s ) 3 = f ( n + s ) 3 (39) , and hence
( F 3 r ( f 3 ) ) ( n ) = ( F 3 r h ) ( 0 ) ∈ Z . (F_3^r(f^3))(n)=(F_3^r h)(0)\in\mathbb{Z}. ( F 3 r ( f 3 )) ( n ) = ( F 3 r h ) ( 0 ) ∈ Z . Since n n n F 3 r ( f 3 ) ∈ Z Z F_3^r(f^3)\in\mathbb{Z}^{\mathbb{Z}} F 3 r ( f 3 ) ∈ Z Z f 3 f^3 f 3 ℓ \ell ℓ
Proof of Corollary 1.3. Suppose f , g f,g f , g p = 2 p=2 p = 2 k ≥ 0 k\ge0 k ≥ 0 p = 2 p=2 p = 2 Theorem 1.2 with ℓ = k \ell=k ℓ = k f g fg f g k k k F 2 k ( f g ) ∈ Z Z F_2^k(fg)\in\mathbb{Z}^{\mathbb{Z}} F 2 k ( f g ) ∈ Z Z f g fg f g
Likewise, if f f f p = 3 p=3 p = 3 Theorem 1.2 for p = 3 p=3 p = 3 ℓ = k \ell=k ℓ = k F 3 k ( f 3 ) ∈ Z Z F_3^k(f^3)\in\mathbb{Z}^{\mathbb{Z}} F 3 k ( f 3 ) ∈ Z Z k ≥ 0 k\ge0 k ≥ 0 f 3 f^3 f 3
Remark 5.1. The polynomial strategy for p = 2 , 3 p=2,3 p = 2 , 3 [2 ] . The proof above supplies the full coefficient estimates and the local lifting argument. The distinction between products and cubes is necessary: for p = 3 p=3 p = 3 f ( n ) = n f(n)=n f ( n ) = n F 3 r f ( n ) = n + r F_3^r f(n)=n+r F 3 r f ( n ) = n + r
( F 3 ( f 2 ) ) ( n ) = n 2 + 2 n + 5 3 (F_3(f^2))(n)=n^2+2n+\frac{5}{3} ( F 3 ( f 2 )) ( n ) = n 2 + 2 n + 3 5 is never integral.
Sharpness for primes greater than three
We now verify zeb’s counterexample from [3 ] and use Theorem 1.1 to identify its first failing depth.
Proposition 6.1 (zeb’s example, with exact failing depth). Let p > 3 p > 3 p > 3 f ( n ) = 1 + n p + 1 f(n) = 1 + n^{p+1} f ( n ) = 1 + n p + 1 f f f f p f^p f p p p p ( p + 1 ) (p+1) ( p + 1 ) F p p + 1 ( f p ) F_p^{p+1}(f^p) F p p + 1 ( f p )
For a first look at the obstruction, take p = 5 p = 5 p = 5
( 1 + x 6 ) 5 = 1 + 5 x 6 + 10 x 12 + 10 x 18 + 5 x 24 + x 30 . (1 + x^6)^5 = 1 + 5x^6 + 10x^{12} + 10x^{18} + 5x^{24} + x^{30}. ( 1 + x 6 ) 5 = 1 + 5 x 6 + 10 x 12 + 10 x 18 + 5 x 24 + x 30 . The polynomial criterion requires two factors of 5 5 5 24 24 24 d ( 24 ) = 6 − 4 = 2 d(24) = 6 - 4 = 2 d ( 24 ) = 6 − 4 = 2 5 5 5 24 24 24
Proof. Since p > 3 p > 3 p > 3 v p ( ( p + 1 ) ! ) = 1 v_p((p + 1)!) = 1 v p (( p + 1 )!) = 1 ⌊ ( p + 1 ) / ( p − 1 ) ⌋ = 1 \left\lfloor(p + 1)/(p - 1) \right\rfloor= 1 ⌊ ( p + 1 ) / ( p − 1 ) ⌋ = 1 d ( p + 1 ) = 0 d(p + 1) = 0 d ( p + 1 ) = 0 Lemma 4.1 (d) shows that n ↦ n p + 1 n \mapsto n^{p+1} n ↦ n p + 1 F p F_p F p 1 1 1 F p k f = 1 + F p k ( n ↦ n p + 1 ) F_p^k f = 1 + F_p^k(n \mapsto n^{p+1}) F p k f = 1 + F p k ( n ↦ n p + 1 ) k ≥ 0 k \ge0 k ≥ 0 f f f f p f^p f p
( 1 + x p + 1 ) p = ∑ r = 0 p ( p r ) ( x p + 1 ) r = ∑ r = 0 p ( p r ) x r ( p + 1 ) . (1 + x^{p+1})^p = \sum_{r=0}^{p} \binom{p}{r}(x^{p+1})^r = \sum_{r=0}^{p} \binom{p}{r}x^{r(p+1)}. ( 1 + x p + 1 ) p = r = 0 ∑ p ( r p ) ( x p + 1 ) r = r = 0 ∑ p ( r p ) x r ( p + 1 ) . The terms with r = 0 r = 0 r = 0 r = p r = p r = p 1 1 1 x p 2 + p x^{p^2+p} x p 2 + p r = p − 1 r = p - 1 r = p − 1 p x ( p − 1 ) ( p + 1 ) px^{(p-1)(p+1)} p x ( p − 1 ) ( p + 1 ) N = p 2 − 1 = ( p − 1 ) ( p + 1 ) N = p^2 - 1 = (p - 1)(p + 1) N = p 2 − 1 = ( p − 1 ) ( p + 1 )
( 1 + x p + 1 ) p = 1 + ∑ r = 1 p − 2 ( p r ) x r ( p + 1 ) + p x N + x p 2 + p . (1 + x^{p+1})^p = 1 + \sum_{r=1}^{p-2} \binom{p}{r}x^{r(p+1)} + px^N + x^{p^2+p}. ( 1 + x p + 1 ) p = 1 + r = 1 ∑ p − 2 ( r p ) x r ( p + 1 ) + p x N + x p 2 + p . For 1 ≤ r ≤ p − 2 1 \le r \le p - 2 1 ≤ r ≤ p − 2 r ( p + 1 ) < p 2 r(p + 1) < p^2 r ( p + 1 ) < p 2
v p ( ( r ( p + 1 ) ) ! ) = r , d ( r ( p + 1 ) ) = ⌊ 2 r p − 1 ⌋ ≤ 1. v_p((r(p + 1))!) = r,\qquad d(r(p + 1)) = \left\lfloor\frac{2r}{p - 1} \right\rfloor\le1. v p (( r ( p + 1 ))!) = r , d ( r ( p + 1 )) = ⌊ p − 1 2 r ⌋ ≤ 1. Also v p ( ( p 2 + p ) ! ) = p + 2 = ⌊ ( p 2 + p ) / ( p − 1 ) ⌋ v_p((p^2 + p)!) = p + 2 = \left\lfloor(p^2 + p)/(p - 1) \right\rfloor v p (( p 2 + p )!) = p + 2 = ⌊ ( p 2 + p ) / ( p − 1 ) ⌋ d ( p 2 + p ) = 0 d(p^2 + p) = 0 d ( p 2 + p ) = 0 1 ≤ r ≤ p − 2 1 \le r \le p - 2 1 ≤ r ≤ p − 2 ( p r ) \binom{p}{r} ( r p ) p p p d ( r ( p + 1 ) ) ≤ 1 d(r(p + 1)) \le1 d ( r ( p + 1 )) ≤ 1 d ( p 2 + p ) = 0 d(p^2 + p) = 0 d ( p 2 + p ) = 0 Lemma 4.1 (d), all the displayed summands except possibly p x N px^N p x N
To test the remaining term p x N px^N p x N x N x^N x N ( x ) N (x)_N ( x ) N N N N
For 0 ≤ j < N 0 \le j < N 0 ≤ j < N j = a p + b j = ap + b j = a p + b 0 ≤ b < p 0 \le b < p 0 ≤ b < p 0 ≤ a ≤ p − 1 0 \le a \le p - 1 0 ≤ a ≤ p − 1 a + b ≤ 2 p − 3 a + b \le2p - 3 a + b ≤ 2 p − 3 a = b = p − 1 a = b = p - 1 a = b = p − 1 j < N j < N j < N v p ( j ! ) = a v_p(j!) = a v p ( j !) = a
d ( j ) = ⌊ a p + b p − 1 ⌋ − a = ⌊ a + b p − 1 ⌋ ≤ 1. d(j) = \left\lfloor\frac{ap + b}{p - 1} \right\rfloor- a = \left\lfloor\frac{a + b}{p - 1} \right\rfloor\le1. d ( j ) = ⌊ p − 1 a p + b ⌋ − a = ⌊ p − 1 a + b ⌋ ≤ 1. Since x N − ( x ) N x^N-(x)_N x N − ( x ) N N N N p ( x N − ( x ) N ) p(x^N-(x)_N) p ( x N − ( x ) N ) p p p d ( j ) ≤ 1 d(j)\le1 d ( j ) ≤ 1 p ( x N − ( x ) N ) p(x^N-(x)_N) p ( x N − ( x ) N )
( 1 + x p + 1 ) p = p ( x ) N + A ( x ) , (40) (1+x^{p+1})^p=p(x)_N+A(x), \tag*{(40)} ( 1 + x p + 1 ) p = p ( x ) N + A ( x ) , (40) where A A A a ( n ) = A ( n ) a(n)=A(n) a ( n ) = A ( n ) h ( n ) = p ( n ) N h(n)=p(n)_N h ( n ) = p ( n ) N (40) at integers gives f p = h + a f^p=h+a f p = h + a
F p k h = F p k ( f p ) − F p k a for all k ≥ 0. F_p^k h=F_p^k(f^p)-F_p^k a \qquad\text{for all } k\ge0. F p k h = F p k ( f p ) − F p k a for all k ≥ 0. Since F p k a F_p^k a F p k a k k k f p f^p f p ( p + 1 ) (p+1) ( p + 1 ) h h h ( p + 1 ) (p+1) ( p + 1 ) Lemma 1.4 , with N = ( p + 1 ) ( p − 1 ) N=(p+1)(p-1) N = ( p + 1 ) ( p − 1 ) Δ N h \Delta^N h Δ N h p ⌊ N / ( p − 1 ) ⌋ Z Z = p p + 1 Z Z p^{\lfloor N/(p-1)\rfloor}\mathbb{Z}^ \mathbb{Z}=p^{p+1}\mathbb{Z}^ \mathbb{Z} p ⌊ N / ( p − 1 )⌋ Z Z = p p + 1 Z Z Δ N ( p ( x ) N ) \Delta^N(p(x)_N) Δ N ( p ( x ) N ) p p + 1 p^{p+1} p p + 1 Δ N ( x ) N \Delta^N(x)_N Δ N ( x ) N p p p^p p p (8) N N N Δ N ( x ) N \Delta^N(x)_N Δ N ( x ) N N ! N! N ! p p p^p p p v p ( N ! ) = p − 1 v_p(N!)=p-1 v p ( N !) = p − 1 f p f^p f p ( p + 1 ) (p+1) ( p + 1 ) Theorem 1.1 shows that f p f^p f p p p p p + 1 p+1 p + 1
Remark 6.2. The proof of Lemma 2.3 also helps explain why the depth p + 1 p+1 p + 1 1 , … , p 1,\ldots,p 1 , … , p P ( x ) p = ∑ j c j ( x ) j P(x)^p=\sum_j c_j(x)_j P ( x ) p = ∑ j c j ( x ) j Δ m ( P p ) ( 0 ) = m ! c m \Delta^m(P^p)(0)=m!c_m Δ m ( P p ) ( 0 ) = m ! c m m = k ( p − 1 ) m=k(p-1) m = k ( p − 1 ) 1 ≤ k ≤ p 1\le k\le p 1 ≤ k ≤ p m ! m! m ! k − 1 k-1 k − 1 p p p p p p c m ∈ p R c_m\in pR c m ∈ pR k = p + 1 k=p+1 k = p + 1 m = p 2 − 1 m=p^2-1 m = p 2 − 1 v p ( m ! ) = p − 1 v_p(m!)=p-1 v p ( m !) = p − 1 Δ m ( P p ) ( 0 ) ∈ p p + 1 R \Delta^m(P^p)(0)\in p^{p+1}R Δ m ( P p ) ( 0 ) ∈ p p + 1 R c m ∈ p 2 R c_m\in p^2R c m ∈ p 2 R c m ∈ p R c_m\in pR c m ∈ pR p p p Proposition 6.1 shows that, for every p > 3 p>3 p > 3
Non-primes
The assumption that the averaging length p p p Theorem 1.1 . Here are some examples of what can go wrong when we average over composite-length windows.
For an integer m ≥ 2 m\ge2 m ≥ 2 F m : Q Z → Q Z F_m:\mathbb{Q}^{\mathbb{Z}}\to\mathbb{Q}^{\mathbb{Z}} F m : Q Z → Q Z
F m f ( n ) = f ( n ) + f ( n + 1 ) + ⋯ + f ( n + m − 1 ) m . F_mf(n)=\frac{f(n)+f(n+1)+\cdots+f(n+m-1)}{m}. F m f ( n ) = m f ( n ) + f ( n + 1 ) + ⋯ + f ( n + m − 1 ) . (generalizing the F p F_p F p m m m f f f m m m F m f F_mf F m f F m f = 0 F_mf=0 F m f = 0 F m k f = 0 F_m^kf=0 F m k f = 0 k ≥ 1 k\ge1 k ≥ 1
Example 7.1. For m = 4 m=4 m = 4 f f f 1 , − 1 , 0 , 0 1,-1,0,0 1 , − 1 , 0 , 0 F 4 f = 0 F_4f=0 F 4 f = 0
F 4 ( f 4 ) = 1 + 1 + 0 + 0 4 = 1 2 . F_4(f^4)=\frac{1+1+0+0}{4}=\frac{1}{2}. F 4 ( f 4 ) = 4 1 + 1 + 0 + 0 = 2 1 . Thus, even when F m k f F_m^k f F m k f k ≥ 0 k \ge0 k ≥ 0 m − 2 m-2 m − 2 m > 2 m>2 m > 2 F m k f = 0 F_m^k f=0 F m k f = 0 F m ( f m ) = 2 / m F_m(f^m)=2/m F m ( f m ) = 2/ m
There is a similar obstruction whenever m m m
Example 7.2. Suppose that r r r r 2 ∣ m r^2 \mid m r 2 ∣ m m m m f f f r r r 1 1 1 − r -r − r r + 1 ≤ r 2 ≤ m r+1 \le r^2 \le m r + 1 ≤ r 2 ≤ m F m k f = 0 F_m^k f=0 F m k f = 0 k ≥ 1 k \ge1 k ≥ 1
F m ( f m ) = r + ( − r ) m m . F_m(f^m)=\frac{r+(-r)^m}{m}. F m ( f m ) = m r + ( − r ) m . The numerator is congruent to r r r r 2 r^2 r 2 m m m f m f^m f m
Odd squarefree lengths can fail as well:
Example 7.3. For m = 15 m=15 m = 15 1 , 1 , − 2 1,1,-2 1 , 1 , − 2 F 15 k f = 0 F_{15}^k f=0 F 15 k f = 0 k ≥ 1 k \ge1 k ≥ 1
F 15 ( f 15 ) = 1 + 1 + ( − 2 ) 15 15 = − 10922 5 ∉ Z . F_{15}(f^{15})=\frac{1+1+(-2)^{15}}{15}=-\frac{10922}{5}\notin\mathbb{Z}. F 15 ( f 15 ) = 15 1 + 1 + ( − 2 ) 15 = − 5 10922 ∈ / Z . Thus the power-preservation assertion fails at the first step even for m = 3 ⋅ 5 m=3\cdot5 m = 3 ⋅ 5
More generally, suppose m ≥ 3 m \ge3 m ≥ 3 a a a a m ≢ a ( m o d m ) a^m \not\equiv a \pmod m a m ≡ a ( mod m ) 0 ≤ a ≤ m − 1 0 \le a \le m-1 0 ≤ a ≤ m − 1 a a a m m m m m m a a a 1 1 1 − a -a − a m − a − 1 m-a-1 m − a − 1 m m m a − a m a-a^m a − a m m m m
Conversely, if
a m ≡ a ( m o d m ) for all a ∈ Z , a^m \equiv a \pmod m \qquad\text{for all }a\in\mathbb{Z}, a m ≡ a ( mod m ) for all a ∈ Z , (that is, m m m f f f
∑ r = 0 m − 1 f ( n + r ) m ≡ ∑ r = 0 m − 1 f ( n + r ) ( m o d m ) for all n ∈ Z . \sum_{r=0}^{m-1} f(n+r)^m \equiv\sum_{r=0}^{m-1} f(n+r) \pmod m \qquad\text{for all }n\in\mathbb{Z}. r = 0 ∑ m − 1 f ( n + r ) m ≡ r = 0 ∑ m − 1 f ( n + r ) ( mod m ) for all n ∈ Z . Consequently, integrality of F m f F_m f F m f F m ( f m ) F_m(f^m) F m ( f m ) m m m a a a
Proposition 7.4. Let m ≥ 2 m \ge2 m ≥ 2
a m ≡ a ( m o d m ) for all a ∈ Z . a^m \equiv a \pmod m \qquad\text{for all }a\in\mathbb{Z}. a m ≡ a ( mod m ) for all a ∈ Z . Let f : Z → Z f:\mathbb{Z}\to\mathbb{Z} f : Z → Z F m f ∈ Z Z F_m f\in\mathbb{Z}^{\mathbb{Z}} F m f ∈ Z Z t ≥ 0 t\ge0 t ≥ 0
F m k ( f m t ) ∈ Z Z for all 0 ≤ k ≤ t + 1. F_m^k(f^{m^t})\in\mathbb{Z}^{\mathbb{Z}} \qquad\text{for all }0\le k\le t+1. F m k ( f m t ) ∈ Z Z for all 0 ≤ k ≤ t + 1. Proof. Subtracting two consecutive averages gives
f ( n + m ) − f ( n ) = m ( ( F m f ) ( n + 1 ) − ( F m f ) ( n ) ) . f(n+m)-f(n)=m\bigl((F_mf)(n+1)-(F_mf)(n)\bigr). f ( n + m ) − f ( n ) = m ( ( F m f ) ( n + 1 ) − ( F m f ) ( n ) ) . Thus
f ( n + m ) ≡ f ( n ) ( m o d m ) for every n ∈ Z (41) f(n+m)\equiv f(n)\pmod m \qquad\text{for every }n\in\mathbb{Z} \tag*{(41)} f ( n + m ) ≡ f ( n ) ( mod m ) for every n ∈ Z (41) (since F m f ∈ Z Z F_mf\in\mathbb{Z}^{\mathbb{Z}} F m f ∈ Z Z
We first check how raising to the m m m a a a b b b a ≡ b ( m o d m r ) a\equiv b\pmod{m^r} a ≡ b ( mod m r ) r ≥ 1 r\ge1 r ≥ 1 a = b + m r u a=b+m^ru a = b + m r u u ∈ Z u\in\mathbb{Z} u ∈ Z a m = ( b + m r u ) m a^m=(b+m^ru)^m a m = ( b + m r u ) m
a m − b m = m r + 1 u b m − 1 + ∑ i = 2 m ( m i ) m r i u i b m − i . a^m-b^m=m^{r+1}ub^{m-1}+\sum_{i=2}^{m}\binom{m}{i}m^{ri}u^ib^{m-i}. a m − b m = m r + 1 u b m − 1 + i = 2 ∑ m ( i m ) m r i u i b m − i . Every term is divisible by m r + 1 m^{r+1} m r + 1 r i ≥ r + 1 ri\ge r+1 r i ≥ r + 1 i ≥ 2 i\ge2 i ≥ 2 a m ≡ b m ( m o d m r + 1 ) a^m\equiv b^m\pmod{m^{r+1}} a m ≡ b m ( mod m r + 1 ) t t t
a m t ≡ b m t ( m o d m r + t ) . a^{m^t}\equiv b^{m^t}\pmod{m^{r+t}}. a m t ≡ b m t ( mod m r + t ) . Thus, from (41) , we obtain
f ( n + m ) m t ≡ f ( n ) m t ( m o d m t + 1 ) for all n ∈ Z . f(n+m)^{m^t}\equiv f(n)^{m^t}\pmod{m^{t+1}}\qquad\text{for all }n\in\mathbb{Z}. f ( n + m ) m t ≡ f ( n ) m t ( mod m t + 1 ) for all n ∈ Z . Let b : Z → Z b:\mathbb{Z}\to\mathbb{Z} b : Z → Z m m m f m t f^{m^t} f m t 0 , 1 , … , m − 1 0,1,\ldots,m-1 0 , 1 , … , m − 1
f m t = b + m t + 1 c f^{m^t}=b+m^{t+1}c f m t = b + m t + 1 c for an integer-valued function c c c Z \mathbb{Z} Z a m ≡ a ( m o d m ) a^m\equiv a\pmod m a m ≡ a ( mod m ) a m t ≡ a ( m o d m ) a^{m^t}\equiv a\pmod m a m t ≡ a ( mod m ) a ∈ Z a\in\mathbb{Z} a ∈ Z
∑ s = 0 m − 1 b ( s ) = ∑ s = 0 m − 1 f ( s ) m t ≡ ∑ s = 0 m − 1 f ( s ) = m ( F m f ) ( 0 ) ≡ 0 ( m o d m ) . \sum_{s=0}^{m-1}b(s)=\sum_{s=0}^{m-1}f(s)^{m^t}\equiv\sum_{s=0}^{m-1}f(s)=m(F_mf)(0)\equiv0\pmod m. s = 0 ∑ m − 1 b ( s ) = s = 0 ∑ m − 1 f ( s ) m t ≡ s = 0 ∑ m − 1 f ( s ) = m ( F m f ) ( 0 ) ≡ 0 ( mod m ) . Since b b b m m m F m b F_mb F m b b b b m k F m k c m^kF_m^kc m k F m k c k k k c c c m t + 1 F m k c m^{t+1}F_m^kc m t + 1 F m k c 0 ≤ k ≤ t + 1 0\le k\le t+1 0 ≤ k ≤ t + 1 F m k F_m^k F m k f m t = b + m t + 1 c f^{m^t}=b+m^{t+1}c f m t = b + m t + 1 c
Example 7.5 (The averaging length 561). The composite integer m = 561 = 3 ⋅ 11 ⋅ 17 m=561=3\cdot11\cdot17 m = 561 = 3 ⋅ 11 ⋅ 17 Proposition 7.4 . Hence, integrality of F 561 f F_{561}f F 561 f Proposition 7.4 ) that the first two averages of f 561 f^{561} f 561 f 561 2 f^{561^2} f 56 1 2 t + 1 t+1 t + 1 f 561 t f^{561^t} f 56 1 t
Keeping the exponent equal to 561, however, does not give preservation at every depth. Take f ( n ) = n f(n)=n f ( n ) = n
( F 561 k f ) ( n ) = n + 280 k for all k ≥ 0 and n ∈ Z , (F_{561}^kf)(n)=n+280k\qquad\text{for all }k\ge0\text{ and }n\in\mathbb{Z}, ( F 561 k f ) ( n ) = n + 280 k for all k ≥ 0 and n ∈ Z , so every average of f f f § 10 ) shows that
∑ a 1 , … , a 5 = 0 560 ( a 1 + ⋯ + a 5 ) 561 ≡ 162 ( m o d 243 ) . (42) \sum_{\substack{a_1,\ldots,a_5=0}}^{560} (a_1+\cdots+a_5)^{561} \equiv162 \pmod{243}. \tag*{(42)} a 1 , … , a 5 = 0 ∑ 560 ( a 1 + ⋯ + a 5 ) 561 ≡ 162 ( mod 243 ) . (42) The left-hand side is 561 5 ( F 561 5 ( f 561 ) ) ( 0 ) 561^5(F_{561}^{5}(f^{561}))(0) 56 1 5 ( F 561 5 ( f 561 )) ( 0 ) (38) ). Since 243 = 3 5 243=3^5 243 = 3 5 561 5 561^5 56 1 5 ( F 561 5 ( f 561 ) ) ( 0 ) (F_{561}^{5}(f^{561}))(0) ( F 561 5 ( f 561 )) ( 0 )
Connections with the literature
The averaging problem also belongs to a longer history of divisibility conditions on finite differences. We describe some connections here, including two results from which parts of our conclusions can be deduced. This section is independent of the proofs above. The paragraphs on p p p
An exact antecedent for the binary product theorem
Sun [4 Definition 2.1] calls a function u : Z ≥ 0 → Z ( p ) u:\mathbb{Z}_{\ge0}\to\mathbb{Z}_{(p)} u : Z ≥ 0 → Z ( p ) p p p
∑ r = 0 j ( − 1 ) r ( j r ) u ( r ) ∈ p j Z ( p ) for all j ≥ 0. \sum_{r=0}^{j}(-1)^r\binom{j}{r}u(r)\in p^j\mathbb{Z}_{(p)}\qquad\text{for all }j\ge0. r = 0 ∑ j ( − 1 ) r ( r j ) u ( r ) ∈ p j Z ( p ) for all j ≥ 0. These sums equal ( − 1 ) j Δ j u ( 0 ) (-1)^j\Delta^j u(0) ( − 1 ) j Δ j u ( 0 ) [4 Theorem 2.3, p. 200] , states that products of p p p p p p p = 2 p=2 p = 2 f , g f,g f , g n ∈ Z n\in\mathbb{Z} n ∈ Z u ( r ) = f ( n + r ) u(r)=f(n+r) u ( r ) = f ( n + r ) v ( r ) = g ( n + r ) v(r)=g(n+r) v ( r ) = g ( n + r ) 2 2 2 q = 1 q=1 q = 1 2 j ∣ Δ j ( f g ) ( n ) 2^j\mid\Delta^j(fg)(n) 2 j ∣ Δ j ( f g ) ( n ) Z ( 2 ) \mathbb{Z}_{(2)} Z ( 2 ) j j j Z \mathbb{Z} Z n n n f g fg f g p = 3 p=3 p = 3 ⌊ j / 2 ⌋ \lfloor j/2\rfloor ⌊ j /2 ⌋ j j j
There is a related formulation using p p p Z p \mathbb{Z}_p Z p p , p 2 , p 3 , … p,p^2,p^3,\ldots p , p 2 , p 3 , … a j → 0 a_j\to0 a j → 0 k k k p k p^k p k R = Z ( p ) R=\mathbb{Z}_{(p)} R = Z ( p )
Kellner [5 Definition 3.1 and Theorem 6.1] studies the p p p K p , 2 K_{p,2} K p , 2 Δ j u ( x ) ∈ p j Z p \Delta^j u(x)\in p^j\mathbb{Z}_p Δ j u ( x ) ∈ p j Z p p = 2 p=2 p = 2 p p p
Mahler expansions and the exact coefficient condition
Newton interpolation has an infinite-series analogue over Z p \mathbb{Z}_p Z p [6 ] identifies continuous functions u : Z p → Z p u:\mathbb{Z}_p\to\mathbb{Z}_p u : Z p → Z p
u ( x ) = ∑ j ≥ 0 a j ( x j ) , a j = Δ j u ( 0 ) ⟶ 0. u(x)=\sum_{j\ge0}a_j\binom{x}{j},\qquad a_j=\Delta^j u(0)\longrightarrow0. u ( x ) = j ≥ 0 ∑ a j ( j x ) , a j = Δ j u ( 0 ) ⟶ 0. This extension procedure also allows us to recover Sun’s earlier product theorem from Kellner’s ring theorem, for every prime p p p u : Z ≥ 0 → R u:\mathbb{Z}_{\geq0}\to R u : Z ≥ 0 → R p p p a j = Δ j u ( 0 ) a_j=\Delta^j u(0) a j = Δ j u ( 0 ) R R R Z p \mathbb{Z}_p Z p a j ∈ p j R a_j\in p^jR a j ∈ p j R
U ( x ) = ∑ j ≥ 0 a j ( x j ) U(x)=\sum_{j\geq0}a_j\binom{x}{j} U ( x ) = j ≥ 0 ∑ a j ( j x ) converges uniformly on Z p \mathbb{Z}_p Z p U ( n ) = u ( n ) U(n)=u(n) U ( n ) = u ( n ) n n n Δ ( x j ) = ( x j − 1 ) \Delta\binom{x}{j}=\binom{x}{j-1} Δ ( j x ) = ( j − 1 x ) j ≥ 1 j\geq1 j ≥ 1
Δ k U ( x ) = ∑ j ≥ k a j ( x j − k ) ∈ p k Z p \Delta^kU(x)=\sum_{j\geq k}a_j\binom{x}{j-k}\in p^k\mathbb{Z}_p Δ k U ( x ) = j ≥ k ∑ a j ( j − k x ) ∈ p k Z p for all k ≥ 0 k\geq0 k ≥ 0 x ∈ Z p x\in\mathbb{Z}_p x ∈ Z p
Here each binomial polynomial takes values in Z p \mathbb{Z}_p Z p p k p^k p k U ∈ K p , 2 U\in\mathcal{K}_{p,2} U ∈ K p , 2 v v v p p p V V V K p , 2 \mathcal{K}_{p,2} K p , 2 U V ∈ K p , 2 UV\in\mathcal{K}_{p,2} U V ∈ K p , 2 Δ k ( u v ) ( 0 ) ∈ p k Z p \Delta^k(uv)(0)\in p^k\mathbb{Z}_p Δ k ( uv ) ( 0 ) ∈ p k Z p R R R R ∩ p k Z p = p k R R\cap p^k\mathbb{Z}_p=p^kR R ∩ p k Z p = p k R u v uv uv p p p
In this language the continuous p p p
a j ∈ p ⌊ j / ( p − 1 ) ⌋ Z p for all j ≥ 0. (43) a_j\in p^{\lfloor j/(p-1)\rfloor}\mathbb{Z}_p\qquad\text{for all }j\geq0. \tag*{(43)} a j ∈ p ⌊ j / ( p − 1 )⌋ Z p for all j ≥ 0. (43) For necessity, apply the difference criterion and evaluate the j j j Δ ( x j ) = ( x j − 1 ) \Delta\binom{x}{j}=\binom{x}{j-1} Δ ( j x ) = ( j − 1 x ) j ≥ 1 j\geq1 j ≥ 1 (8) after division by j ! j! j ! r ( p − 1 ) r(p-1) r ( p − 1 ) r ( p − 1 ) r(p-1) r ( p − 1 ) (33) . Every remaining coefficient is divisible by p r p^r p r p r p^r p r Z p \mathbb{Z}_p Z p
Every average-integral function has such a continuous extension, including agreement at negative integers. Here is a direct justification of the latter point. The bounds on a j = Δ j f ( 0 ) a_j=\Delta^j f(0) a j = Δ j f ( 0 ) f f f n n n
A j = Δ j f ( n ) , P N ( x ) = ∑ j = 0 N A j ( x − n j ) . A_j=\Delta^j f(n),\qquad P_N(x)=\sum_{j=0}^{N}A_j\binom{x-n}{j}. A j = Δ j f ( n ) , P N ( x ) = j = 0 ∑ N A j ( j x − n ) . The same bounds give a uniform limit u n u_n u n Z p \mathbb{Z}_p Z p u n ( x ) = f ( x ) u_n(x)=f(x) u n ( x ) = f ( x ) x ≥ n x\geq n x ≥ n u n u_n u n Z ≥ 0 \mathbb{Z}_{\geq0} Z ≥ 0 n n n (43) is average-integral whenever its values on Z \mathbb{Z} Z
A second proof using Stirling numbers
The Stirling number S ( N , m ) S(N,m) S ( N , m ) N N N m m m
x N = ∑ m = 0 N S ( N , m ) ( x ) m . x^N=\sum_{m=0}^{N}S(N,m)(x)_m. x N = m = 0 ∑ N S ( N , m ) ( x ) m . For a nonnegative integer x x x N N N x x x x x x S ( N , m ) S(N,m) S ( N , m )
In [7 Lemma 2.1] , Adelberg proves a lower bound on v p ( S ( N , m ) ) v_p(S(N,m)) v p ( S ( N , m ))
v p ( S ( N , m ) ) ≥ v p ( N ! ) − v p ( m ! ) − ⌊ N − m p − 1 ⌋ (44) v_p(S(N,m)) \ge v_p(N!) - v_p(m!) - \left\lfloor\frac{N-m}{p-1} \right\rfloor \tag*{(44)} v p ( S ( N , m )) ≥ v p ( N !) − v p ( m !) − ⌊ p − 1 N − m ⌋ (44) for all N ≥ m ≥ 1 N \ge m \ge1 N ≥ m ≥ 1 Theorem 1.1 , as follows.
Let f f f ℓ \ell ℓ 1 ≤ ℓ ≤ p 1 \le\ell\le p 1 ≤ ℓ ≤ p n ∈ Z n \in\mathbb{Z} n ∈ Z Lemma 4.4 supplies an integer-valued polynomial P ∈ M p P \in M_p P ∈ M p P ( r ) = f ( n + r ) P(r)=f(n+r) P ( r ) = f ( n + r ) 0 ≤ r ≤ ℓ ( p − 1 ) 0 \le r \le\ell(p-1) 0 ≤ r ≤ ℓ ( p − 1 ) P ( x ) = ∑ j c j x j P(x)=\sum_j c_jx^j P ( x ) = ∑ j c j x j M p M_p M p c j ∈ p d ( j ) R c_j \in p^{d(j)}R c j ∈ p d ( j ) R d ( j ) ≥ 0 d(j) \ge0 d ( j ) ≥ 0 p p p
P ‾ ( x ) = ∑ j : d ( j ) = 0 c j ‾ x j . \overline{P}(x)=\sum_{j:d(j)=0}\overline{c_j}x^j. P ( x ) = j : d ( j ) = 0 ∑ c j x j . In characteristic p p p ( p a ) \binom{p}{a} ( a p ) 1 ≤ a < p 1 \le a < p 1 ≤ a < p ( U + V ) p = U p + V p (U+V)^p=U^p+V^p ( U + V ) p = U p + V p
P ‾ ( x ) p = ∑ j : d ( j ) = 0 c j ‾ p x p j = ∑ j : d ( j ) = 0 c j ‾ x p j . \overline{P}(x)^p=\sum_{j:d(j)=0}\overline{c_j}^{\,p}x^{pj}=\sum_{j:d(j)=0}\overline{c_j}x^{pj}. P ( x ) p = j : d ( j ) = 0 ∑ c j p x p j = j : d ( j ) = 0 ∑ c j x p j . The last equality uses c ‾ p = c ‾ \overline{c}^p=\overline{c} c p = c F p \mathbb{F}_p F p N = p j N=pj N = p j d ( N ) = d ( j ) = 0 d(N)=d(j)=0 d ( N ) = d ( j ) = 0 Lemma 4.1 (b).
As in the elementary proof, we want the falling-factorial coefficient at m = k ( p − 1 ) m=k(p-1) m = k ( p − 1 ) p p p p p p p p p m = k ( p − 1 ) m=k(p-1) m = k ( p − 1 ) 1 ≤ k ≤ p 1 \le k \le p 1 ≤ k ≤ p v p ( m ! ) = k − 1 v_p(m!)=k-1 v p ( m !) = k − 1 (44) simplifies to
v p ( N ! ) − ( k − 1 ) − ( ⌊ N p − 1 ⌋ − k ) = 1 − d ( N ) . v_p(N!)-(k-1)-\left(\left\lfloor\frac{N}{p-1}\right\rfloor-k\right)=1-d(N). v p ( N !) − ( k − 1 ) − ( ⌊ p − 1 N ⌋ − k ) = 1 − d ( N ) . Taking N = p j N=pj N = p j p ∣ S ( p j , m ) p\mid S(pj,m) p ∣ S ( p j , m ) p j ≥ m pj\ge m p j ≥ m d ( j ) = 0 d(j)=0 d ( j ) = 0 p j < m pj<m p j < m
[ ( x ) m ] ( P p ‾ ) = ∑ j : d ( j ) = 0 c j ‾ S ( p j , m ) ‾ = 0. [(x)_m](\overline{P^p})=\sum_{j:d(j)=0}\overline{c_j}\,\overline{S(pj,m)}=0. [( x ) m ] ( P p ) = j : d ( j ) = 0 ∑ c j S ( p j , m ) = 0. Thus, if b m b_m b m ( x ) m (x)_m ( x ) m P p P^p P p b m ∈ p R b_m\in pR b m ∈ pR (9) ,
Δ m ( P p ) ( 0 ) = m ! b m ∈ p k R , \Delta^m(P^p)(0)=m!b_m\in p^kR, Δ m ( P p ) ( 0 ) = m ! b m ∈ p k R , since v p ( m ! ) = k − 1 v_p(m!)=k-1 v p ( m !) = k − 1 1 ≤ k ≤ ℓ 1 \le k \le\ell 1 ≤ k ≤ ℓ m = k ( p − 1 ) ≤ ℓ ( p − 1 ) m=k(p-1)\le\ell(p-1) m = k ( p − 1 ) ≤ ℓ ( p − 1 ) P p P^p P p r ↦ f ( n + r ) p r\mapsto f(n+r)^p r ↦ f ( n + r ) p r = 0 , … , m r=0,\ldots,m r = 0 , … , m (21) gives
Δ k ( p − 1 ) ( f p ) ( n ) = Δ m ( P p ) ( 0 ) ∈ p k R . \Delta^{k(p-1)}(f^p)(n)=\Delta^m(P^p)(0)\in p^kR. Δ k ( p − 1 ) ( f p ) ( n ) = Δ m ( P p ) ( 0 ) ∈ p k R . The left side is an integer, so it is divisible by p k p^{k} p k n n n k k k Lemma 1.4 gives F p k ( f p ) ∈ Z Z F_{p}^{k}(f^{p}) \in\mathbb{Z}^{\mathbb{Z}} F p k ( f p ) ∈ Z Z 0 ≤ k ≤ ℓ 0 \leq k \leq\ell 0 ≤ k ≤ ℓ ℓ = 0 \ell= 0 ℓ = 0 f f f
Thus the finite-depth conclusion can be deduced from this published valuation bound and the polynomial criterion already present in the 2011 MathOverflow discussion. The proof in § 2 gives a direct finite-field argument for the particular vanishing needed here.
Power sums over a prime field
We prove (18) , working throughout in F p \mathbb{F}_{p} F p
When b = 0 b = 0 b = 0 r 0 = 1 r^{0} = 1 r 0 = 1 p p p F p \mathbb{F}_{p} F p b = p − 1 b = p - 1 b = p − 1 r p − 1 = 1 r^{p-1} = 1 r p − 1 = 1 r r r 0 p − 1 = 0 0^{p-1} = 0 0 p − 1 = 0 p − 1 = − 1 p - 1 = -1 p − 1 = − 1 F p \mathbb{F}_{p} F p
It remains to consider 1 ≤ b < p − 1 1 \leq b < p - 1 1 ≤ b < p − 1 a a a a b ≠ 1 a^{b} \ne1 a b = 1 X b − 1 X^{b} - 1 X b − 1 b b b p − 1 p - 1 p − 1 S = ∑ r ∈ F p r b S = \sum_{r \in\mathbb{F}_{p}} r^{b} S = ∑ r ∈ F p r b a a a F p \mathbb{F}_{p} F p
S = ∑ r ∈ F p ( a r ) b = a b ∑ r ∈ F p r b = a b S . S = \sum_{r \in\mathbb{F}_{p}} (ar)^{b} = a^{b} \sum_{r \in\mathbb{F}_{p}} r^{b} = a^{b}S. S = r ∈ F p ∑ ( a r ) b = a b r ∈ F p ∑ r b = a b S . Since a b − 1 ≠ 0 a^{b} - 1 \ne0 a b − 1 = 0 F p \mathbb{F}_{p} F p S = 0 S = 0 S = 0
Verification of Example 7.5
The following exact computation in Python verifies (42) . After r r r counts[s] is, modulo 243, the number of r r r { 0 , 1 , … , 560 } \{0,1,\ldots,560\} { 0 , 1 , … , 560 } s s s a a a s s s s 561 s^{561} s 561
modulus = 243
counts = [1] + [0] * (modulus - 1)
for r in range(5):
counts = [
sum(counts[(s - a) % modulus] for a in range(561)) % modulus
for s in range(modulus)
]
remainder = sum(counts[s] * pow(s, 561, modulus)
for s in range(modulus)) % modulus
assert remainder == 162This establishes failure of average-integrality by the fifth step; it does not assert that the fifth step is the first failure.
References 