= Weyl differencing
{c}
Taking a <finite difference> lowers the degree of a <polynomial> phase. For $S(\theta)=\sum_{x=1}^n e(\theta P(x))$, expand $|S|^2$ by shifts $h$ and apply the <Cauchy-Schwarz inequality> to those shift sums. This gives $|S|^4\le2n\sum_{h,l}\sum_{x\in I_{h,l}}e(\theta\Delta_h\Delta_lP(x))$, where $I_{h,l}$ enforces that $x,x+h,x+l,x+h+l$ lie in $[1,n]$. Although individual terms can be complex, the entire sum is real and nonnegative because it equals a sum of squares. For $P(x)=x^3$, the phase is $3hl(2x+h+l)$.
Back to article page
