Skip to main content
deleted 4 characters in body
Source Link
Will Sawin
  • 148.7k
  • 9
  • 324
  • 563

We can estimate this using the Polya-Vinagradov method. We get a main term, which comes from the fact that two elements of $\mathbb F_p$ that sum to something greater than $p$ are more likely to sum to something a little bit greater than $p$ than a lot, and an error term. The formula is:

$$ \frac{ i p}{2\pi} + O( \sqrt{p}\log{p} )$$

View the sum as a sum of the product of two characteristic functions and an exponential funcion:

$$\sum_{x,y\in \mathbb F_p}\mathbf 1_{\{xy=1\} } e(x+y) \mathbf 1_{\{x+y>p\}}$$

Let $f(a,b)$ be the Fourier transform of $\mathbf 1_{\{xy=1\} }$. Let $g(a,b)$ be the Fourier transform of $\mathbf 1_{\{x+y>p\}}$. Then by Plancherel's formula, this sum is:

$$\frac{\sum_{a,b\in \mathbb F_p} f(a+1,b+1) \overline{g} ( a,b)}{p^2} $$

This sum, it turns out, is easier to estimate. Our first function:

$$f(a,b) = \sum_{x \in \mathbb F_p} e(ax+ bx^{-1} ) = K(ab)$$

is a Kloosterman sum, unless $a=0$ or $b=0$, in which case it is $-1$, unless both $a$ and $b$ are $0$, in which case it is $p-1$. In particular, it is bounded by $2 \sqrt{p}$, unless $a=b=0$, in which case it is $p-1$.

Our second sum we may estimate by more elementary means:

$$g(a,b) = \sum_{0\leq x,y<p, x+y>p} e(ax + by) = \sum_{1\leq x <p} e(ax) \left( \sum_{p+1-x \leq y \leq p-1} e(by) \right) =\sum_{1\leq x <p} e(ax) \frac{ e(bp) - e(b (p+1-x))}{e(b)-1}= \frac{\sum_{1\leq x< p} e(ax+bp) }{e(b)-1} + \frac{\sum_{1\leq x< p} e((a-b) x+b) }{e(b)-1} $$

The first term depends on whether $a=0$, equaling $\frac{(p-1) e(bp)}{e(b)-1)}$$\frac{(p-1) e(bp)}{e(b)-1}$ if $a=0$ and $\frac{- e(bp)}{e(b)-1)}$$\frac{- e(bp)}{e(b)-1}$ otherwise. The second term depends on whether $a=b$, equallingequaling $\frac{(p-1) e(bp)}{e(b)-1)}$$\frac{(p-1) e(bp)}{e(b)-1}$ if $a=b$ and $\frac{- e(bp)}{e(b)-1)}$$\frac{- e(bp)}{e(b)-1}$ otherwise. The whole equation is wrong if $b=0$, but we can use symmetry to handle that, unlesunless $a=0$ and $b=0$, in which case the sum is obviously $(p-1)(p-2)/2$.

Altogether, the $L_1$-norm of $g$ is $O(p^2 \log p)$. Since each term of $f$ but one is bounded by $2\sqrt{p}$, this gives a contribution of at most $\sqrt{p} \log{p}$. This is the error term.

The leading term comes from $f(0,0)$, which is $p-1$, summing against $\overline{g}(-1,-1)$, which is $- p e(1) / (e(1)-1)=\frac{i p^2}{2 \pi} + O(p)$. This gives a contribution of $ip/2\pi+O(1)$

We can estimate this using the Polya-Vinagradov method. We get a main term, which comes from the fact that two elements of $\mathbb F_p$ that sum to something greater than $p$ are more likely to sum to something a little bit greater than $p$ than a lot, and an error term. The formula is:

$$ \frac{ i p}{2\pi} + O( \sqrt{p}\log{p} )$$

View the sum as a sum of the product of two characteristic functions and an exponential funcion:

$$\sum_{x,y\in \mathbb F_p}\mathbf 1_{\{xy=1\} } e(x+y) \mathbf 1_{\{x+y>p\}}$$

Let $f(a,b)$ be the Fourier transform of $\mathbf 1_{\{xy=1\} }$. Let $g(a,b)$ be the Fourier transform of $\mathbf 1_{\{x+y>p\}}$. Then by Plancherel's formula, this sum is:

$$\frac{\sum_{a,b\in \mathbb F_p} f(a+1,b+1) \overline{g} ( a,b)}{p^2} $$

This sum, it turns out, is easier to estimate. Our first function:

$$f(a,b) = \sum_{x \in \mathbb F_p} e(ax+ bx^{-1} ) = K(ab)$$

is a Kloosterman sum, unless $a=0$ or $b=0$, in which case it is $-1$, unless both $a$ and $b$ are $0$, in which case it is $p-1$. In particular, it is bounded by $2 \sqrt{p}$, unless $a=b=0$, in which case it is $p-1$.

Our second sum we may estimate by more elementary means:

$$g(a,b) = \sum_{0\leq x,y<p, x+y>p} e(ax + by) = \sum_{1\leq x <p} e(ax) \left( \sum_{p+1-x \leq y \leq p-1} e(by) \right) =\sum_{1\leq x <p} e(ax) \frac{ e(bp) - e(b (p+1-x))}{e(b)-1}= \frac{\sum_{1\leq x< p} e(ax+bp) }{e(b)-1} + \frac{\sum_{1\leq x< p} e((a-b) x+b) }{e(b)-1} $$

The first term depends on whether $a=0$, equaling $\frac{(p-1) e(bp)}{e(b)-1)}$ if $a=0$ and $\frac{- e(bp)}{e(b)-1)}$ otherwise. The second term depends on whether $a=b$, equalling $\frac{(p-1) e(bp)}{e(b)-1)}$ if $a=b$ and $\frac{- e(bp)}{e(b)-1)}$ otherwise. The whole equation is wrong if $b=0$, but we can use symmetry to handle that, unles $a=0$ and $b=0$, in which case the sum is obviously $(p-1)(p-2)/2$.

Altogether, the $L_1$-norm of $g$ is $O(p^2 \log p)$. Since each term of $f$ but one is bounded by $2\sqrt{p}$, this gives a contribution of at most $\sqrt{p} \log{p}$. This is the error term.

The leading term comes from $f(0,0)$, which is $p-1$, summing against $\overline{g}(-1,-1)$, which is $- p e(1) / (e(1)-1)=\frac{i p^2}{2 \pi} + O(p)$. This gives a contribution of $ip/2\pi+O(1)$

We can estimate this using the Polya-Vinagradov method. We get a main term, which comes from the fact that two elements of $\mathbb F_p$ that sum to something greater than $p$ are more likely to sum to something a little bit greater than $p$ than a lot, and an error term. The formula is:

$$ \frac{ i p}{2\pi} + O( \sqrt{p}\log{p} )$$

View the sum as a sum of the product of two characteristic functions and an exponential funcion:

$$\sum_{x,y\in \mathbb F_p}\mathbf 1_{\{xy=1\} } e(x+y) \mathbf 1_{\{x+y>p\}}$$

Let $f(a,b)$ be the Fourier transform of $\mathbf 1_{\{xy=1\} }$. Let $g(a,b)$ be the Fourier transform of $\mathbf 1_{\{x+y>p\}}$. Then by Plancherel's formula, this sum is:

$$\frac{\sum_{a,b\in \mathbb F_p} f(a+1,b+1) \overline{g} ( a,b)}{p^2} $$

This sum, it turns out, is easier to estimate. Our first function:

$$f(a,b) = \sum_{x \in \mathbb F_p} e(ax+ bx^{-1} ) = K(ab)$$

is a Kloosterman sum, unless $a=0$ or $b=0$, in which case it is $-1$, unless both $a$ and $b$ are $0$, in which case it is $p-1$. In particular, it is bounded by $2 \sqrt{p}$, unless $a=b=0$, in which case it is $p-1$.

Our second sum we may estimate by more elementary means:

$$g(a,b) = \sum_{0\leq x,y<p, x+y>p} e(ax + by) = \sum_{1\leq x <p} e(ax) \left( \sum_{p+1-x \leq y \leq p-1} e(by) \right) =\sum_{1\leq x <p} e(ax) \frac{ e(bp) - e(b (p+1-x))}{e(b)-1}= \frac{\sum_{1\leq x< p} e(ax+bp) }{e(b)-1} + \frac{\sum_{1\leq x< p} e((a-b) x+b) }{e(b)-1} $$

The first term depends on whether $a=0$, equaling $\frac{(p-1) e(bp)}{e(b)-1}$ if $a=0$ and $\frac{- e(bp)}{e(b)-1}$ otherwise. The second term depends on whether $a=b$, equaling $\frac{(p-1) e(bp)}{e(b)-1}$ if $a=b$ and $\frac{- e(bp)}{e(b)-1}$ otherwise. The whole equation is wrong if $b=0$, but we can use symmetry to handle that, unless $a=0$ and $b=0$, in which case the sum is obviously $(p-1)(p-2)/2$.

Altogether, the $L_1$-norm of $g$ is $O(p^2 \log p)$. Since each term of $f$ but one is bounded by $2\sqrt{p}$, this gives a contribution of at most $\sqrt{p} \log{p}$. This is the error term.

The leading term comes from $f(0,0)$, which is $p-1$, summing against $\overline{g}(-1,-1)$, which is $- p e(1) / (e(1)-1)=\frac{i p^2}{2 \pi} + O(p)$. This gives a contribution of $ip/2\pi+O(1)$

added 2 characters in body
Source Link
Will Sawin
  • 148.7k
  • 9
  • 324
  • 563

We can estimate this using the Polya-Vinagradov method. We get a main term, which comes from the fact that two elements of $\mathbb F_p$ that sum to something greater than $p$ are more likely to sum to something a little bit greater than $p$ than a lot, and an error term. The formula is:

$$ \frac{ i p}{2\pi} + O( \sqrt{p}\log{p} )$$

View the sum as a sum of the product of two characteristic functions and an exponential funcion:

$$\sum_{x,y\in \mathbb F_p}\mathbf 1_{\{xy=1\} } e(x+y) \mathbf 1_{\{x+y>p\}}$$

Let $f(a,b)$ be the Fourier transform of $\mathbf 1_{\{xy=1\} }$. Let $g(a,b)$ be the Fourier transform of $\mathbf 1_{\{x+y>p\}}$. Then by Plancherel's formula, this sum is:

$$\frac{\sum_{a,b\in \mathbb F_p} f(a-1,b-1) \overline{g} ( a,b)}{p^2} $$$$\frac{\sum_{a,b\in \mathbb F_p} f(a+1,b+1) \overline{g} ( a,b)}{p^2} $$

This sum, it turns out, is easier to estimate. Our first function:

$$f(a,b) = \sum_{x \in \mathbb F_p} e(ax+ bx^{-1} ) = K(ab)$$

is a Kloosterman sum, unless $a=0$ or $b=0$, in which case it is $-1$, unless both $a$ and $b$ are $0$, in which case it is $p-1$. In particular, it is bounded by $2 \sqrt{p}$, unless $a=b=0$, in which case it is $p-1$.

Our second sum we may estimate by more elementary means:

$$g(a,b) = \sum_{0\leq x,y<p, x+y>p} e(ax + by) = \sum_{1\leq x <p} e(ax) \left( \sum_{p+1-x \leq y \leq p-1} e(by) \right) =\sum_{1\leq x <p} e(ax) \frac{ e(bp) - e(b (p+1-x))}{e(b)-1}= \frac{\sum_{1\leq x< p} e(ax+bp) }{e(b)-1} + \frac{\sum_{1\leq x< p} e((a-b) x+b) }{e(b)-1} $$

The first term depends on whether $a=0$, equaling $\frac{(p-1) e(bp)}{e(b)-1)}$ if $a=0$ and $\frac{- e(bp)}{e(b)-1)}$ otherwise. The second term depends on whether $a=b$, equalling $\frac{(p-1) e(bp)}{e(b)-1)}$ if $a=b$ and $\frac{- e(bp)}{e(b)-1)}$ otherwise. The whole equation is wrong if $b=0$, but we can use symmetry to handle that, unles $a=0$ and $b=0$, in which case the sum is obviously $(p-1)(p-2)/2$.

Altogether, the $L_1$-norm of $g$ is $O(p^2 \log p)$. Since each term of $f$ but one is bounded by $2\sqrt{p}$, this gives a contribution of at most $\sqrt{p} \log{p}$. This is the error term.

The leading term comes from $f(0,0)$, which is $p$$p-1$, summing against $\overline{g}(-1,-1)$, which is $- p e(1) / (e(1)-1)=\frac{i p^2}{2 \pi} + O(p)$. This gives a contribution of $ip/2\pi+O(1)$

We can estimate this using the Polya-Vinagradov method. We get a main term, which comes from the fact that two elements of $\mathbb F_p$ that sum to something greater than $p$ are more likely to sum to something a little bit greater than $p$ than a lot, and an error term. The formula is:

$$ \frac{ i p}{2\pi} + O( \sqrt{p}\log{p} )$$

View the sum as a sum of the product of two characteristic functions and an exponential funcion:

$$\sum_{x,y\in \mathbb F_p}\mathbf 1_{\{xy=1\} } e(x+y) \mathbf 1_{\{x+y>p\}}$$

Let $f(a,b)$ be the Fourier transform of $\mathbf 1_{\{xy=1\} }$. Let $g(a,b)$ be the Fourier transform of $\mathbf 1_{\{x+y>p\}}$. Then by Plancherel's formula, this sum is:

$$\frac{\sum_{a,b\in \mathbb F_p} f(a-1,b-1) \overline{g} ( a,b)}{p^2} $$

This sum, it turns out, is easier to estimate. Our first function:

$$f(a,b) = \sum_{x \in \mathbb F_p} e(ax+ bx^{-1} ) = K(ab)$$

is a Kloosterman sum, unless $a=0$ or $b=0$, in which case it is $-1$, unless both $a$ and $b$ are $0$, in which case it is $p-1$. In particular, it is bounded by $2 \sqrt{p}$, unless $a=b=0$, in which case it is $p-1$.

Our second sum we may estimate by more elementary means:

$$g(a,b) = \sum_{0\leq x,y<p, x+y>p} e(ax + by) = \sum_{1\leq x <p} e(ax) \left( \sum_{p+1-x \leq y \leq p-1} e(by) \right) =\sum_{1\leq x <p} e(ax) \frac{ e(bp) - e(b (p+1-x))}{e(b)-1}= \frac{\sum_{1\leq x< p} e(ax+bp) }{e(b)-1} + \frac{\sum_{1\leq x< p} e((a-b) x+b) }{e(b)-1} $$

The first term depends on whether $a=0$, equaling $\frac{(p-1) e(bp)}{e(b)-1)}$ if $a=0$ and $\frac{- e(bp)}{e(b)-1)}$ otherwise. The second term depends on whether $a=b$, equalling $\frac{(p-1) e(bp)}{e(b)-1)}$ if $a=b$ and $\frac{- e(bp)}{e(b)-1)}$ otherwise. The whole equation is wrong if $b=0$, but we can use symmetry to handle that, unles $a=0$ and $b=0$, in which case the sum is obviously $(p-1)(p-2)/2$.

Altogether, the $L_1$-norm of $g$ is $O(p^2 \log p)$. Since each term of $f$ but one is bounded by $2\sqrt{p}$, this gives a contribution of at most $\sqrt{p} \log{p}$. This is the error term.

The leading term comes from $f(0,0)$, which is $p$, summing against $\overline{g}(-1,-1)$, which is $- p e(1) / (e(1)-1)=\frac{i p^2}{2 \pi} + O(p)$. This gives a contribution of $ip/2\pi+O(1)$

We can estimate this using the Polya-Vinagradov method. We get a main term, which comes from the fact that two elements of $\mathbb F_p$ that sum to something greater than $p$ are more likely to sum to something a little bit greater than $p$ than a lot, and an error term. The formula is:

$$ \frac{ i p}{2\pi} + O( \sqrt{p}\log{p} )$$

View the sum as a sum of the product of two characteristic functions and an exponential funcion:

$$\sum_{x,y\in \mathbb F_p}\mathbf 1_{\{xy=1\} } e(x+y) \mathbf 1_{\{x+y>p\}}$$

Let $f(a,b)$ be the Fourier transform of $\mathbf 1_{\{xy=1\} }$. Let $g(a,b)$ be the Fourier transform of $\mathbf 1_{\{x+y>p\}}$. Then by Plancherel's formula, this sum is:

$$\frac{\sum_{a,b\in \mathbb F_p} f(a+1,b+1) \overline{g} ( a,b)}{p^2} $$

This sum, it turns out, is easier to estimate. Our first function:

$$f(a,b) = \sum_{x \in \mathbb F_p} e(ax+ bx^{-1} ) = K(ab)$$

is a Kloosterman sum, unless $a=0$ or $b=0$, in which case it is $-1$, unless both $a$ and $b$ are $0$, in which case it is $p-1$. In particular, it is bounded by $2 \sqrt{p}$, unless $a=b=0$, in which case it is $p-1$.

Our second sum we may estimate by more elementary means:

$$g(a,b) = \sum_{0\leq x,y<p, x+y>p} e(ax + by) = \sum_{1\leq x <p} e(ax) \left( \sum_{p+1-x \leq y \leq p-1} e(by) \right) =\sum_{1\leq x <p} e(ax) \frac{ e(bp) - e(b (p+1-x))}{e(b)-1}= \frac{\sum_{1\leq x< p} e(ax+bp) }{e(b)-1} + \frac{\sum_{1\leq x< p} e((a-b) x+b) }{e(b)-1} $$

The first term depends on whether $a=0$, equaling $\frac{(p-1) e(bp)}{e(b)-1)}$ if $a=0$ and $\frac{- e(bp)}{e(b)-1)}$ otherwise. The second term depends on whether $a=b$, equalling $\frac{(p-1) e(bp)}{e(b)-1)}$ if $a=b$ and $\frac{- e(bp)}{e(b)-1)}$ otherwise. The whole equation is wrong if $b=0$, but we can use symmetry to handle that, unles $a=0$ and $b=0$, in which case the sum is obviously $(p-1)(p-2)/2$.

Altogether, the $L_1$-norm of $g$ is $O(p^2 \log p)$. Since each term of $f$ but one is bounded by $2\sqrt{p}$, this gives a contribution of at most $\sqrt{p} \log{p}$. This is the error term.

The leading term comes from $f(0,0)$, which is $p-1$, summing against $\overline{g}(-1,-1)$, which is $- p e(1) / (e(1)-1)=\frac{i p^2}{2 \pi} + O(p)$. This gives a contribution of $ip/2\pi+O(1)$

Source Link
Will Sawin
  • 148.7k
  • 9
  • 324
  • 563

We can estimate this using the Polya-Vinagradov method. We get a main term, which comes from the fact that two elements of $\mathbb F_p$ that sum to something greater than $p$ are more likely to sum to something a little bit greater than $p$ than a lot, and an error term. The formula is:

$$ \frac{ i p}{2\pi} + O( \sqrt{p}\log{p} )$$

View the sum as a sum of the product of two characteristic functions and an exponential funcion:

$$\sum_{x,y\in \mathbb F_p}\mathbf 1_{\{xy=1\} } e(x+y) \mathbf 1_{\{x+y>p\}}$$

Let $f(a,b)$ be the Fourier transform of $\mathbf 1_{\{xy=1\} }$. Let $g(a,b)$ be the Fourier transform of $\mathbf 1_{\{x+y>p\}}$. Then by Plancherel's formula, this sum is:

$$\frac{\sum_{a,b\in \mathbb F_p} f(a-1,b-1) \overline{g} ( a,b)}{p^2} $$

This sum, it turns out, is easier to estimate. Our first function:

$$f(a,b) = \sum_{x \in \mathbb F_p} e(ax+ bx^{-1} ) = K(ab)$$

is a Kloosterman sum, unless $a=0$ or $b=0$, in which case it is $-1$, unless both $a$ and $b$ are $0$, in which case it is $p-1$. In particular, it is bounded by $2 \sqrt{p}$, unless $a=b=0$, in which case it is $p-1$.

Our second sum we may estimate by more elementary means:

$$g(a,b) = \sum_{0\leq x,y<p, x+y>p} e(ax + by) = \sum_{1\leq x <p} e(ax) \left( \sum_{p+1-x \leq y \leq p-1} e(by) \right) =\sum_{1\leq x <p} e(ax) \frac{ e(bp) - e(b (p+1-x))}{e(b)-1}= \frac{\sum_{1\leq x< p} e(ax+bp) }{e(b)-1} + \frac{\sum_{1\leq x< p} e((a-b) x+b) }{e(b)-1} $$

The first term depends on whether $a=0$, equaling $\frac{(p-1) e(bp)}{e(b)-1)}$ if $a=0$ and $\frac{- e(bp)}{e(b)-1)}$ otherwise. The second term depends on whether $a=b$, equalling $\frac{(p-1) e(bp)}{e(b)-1)}$ if $a=b$ and $\frac{- e(bp)}{e(b)-1)}$ otherwise. The whole equation is wrong if $b=0$, but we can use symmetry to handle that, unles $a=0$ and $b=0$, in which case the sum is obviously $(p-1)(p-2)/2$.

Altogether, the $L_1$-norm of $g$ is $O(p^2 \log p)$. Since each term of $f$ but one is bounded by $2\sqrt{p}$, this gives a contribution of at most $\sqrt{p} \log{p}$. This is the error term.

The leading term comes from $f(0,0)$, which is $p$, summing against $\overline{g}(-1,-1)$, which is $- p e(1) / (e(1)-1)=\frac{i p^2}{2 \pi} + O(p)$. This gives a contribution of $ip/2\pi+O(1)$