Jump to content

Talk:Gaussian period

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Untitled

[edit]

I have my suspicions that the notation "(a, n)" means gcd(a,n) - is this correct? Dysprosia 10:02, 9 Feb 2004 (UTC)

Yes, that's right.

Charles Matthews 11:29, 9 Feb 2004 (UTC)

Thanks to all who have worked on the format here. Caveat: what is good for one browser may not be good for all.

Charles Matthews 17:25, 9 Feb 2004 (UTC)

I just found the oddly-titled Number-theoretic transform. Perhaps that article should be renamed to "Gauss sum", with some of the content from there moved there, while this article takes a more abstract approach? I suggest this, because merging the two might result in an over-long article. linas 06:48, 9 February 2006 (UTC)[reply]

But it's not about Gauss sums. Charles Matthews 08:25, 9 February 2006 (UTC)[reply]
Hmm, well, then I'll need to take a look. I was under the impression that any sum with exp(i\pi jk/n) in it was a "gauss sum". I'll look it up. linas 01:01, 10 February 2006 (UTC)[reply]
OK, I removed the merge tag. I guess I was dazed and confused. linas 04:15, 10 February 2006 (UTC)[reply]

Unclear content

[edit]

I read in the "Example" section that:

"Evaluating the square of the sum P is connected with the problem of counting how many quadratic residues between 1 and p − 1 are succeeded by quadratic residues. The solution is elementary (as we would now say, it computes a local zeta-function, for a curve that is a conic.)"

This is really unclear to me and I don't think it helps for most reader at all. Can someone please add more details in this part?

Breakfastisready (talk) 13:19, 5 April 2019 (UTC)[reply]

Matricec (talk) 00:54, 24 May 2021 (UTC)[reply]

I do not intend to change anything here.

Sine and cosine formulae with odd prime numbers

[edit]

Matricec (talk) 01:04, 7 January 2023 (UTC)[reply]

Let x, y be variables. Let z be a complex number. Let α, β, θ be real numbers.

Let s be an integer. Let a, b, c, d, f, h, i, j, k, l, m, t, u, v, w be positive integers.

Let o be a prime number and o=2h+1 for h≥1. Let p, q be prime numbers and p≡3(mod 4), q≡1(mod 4).

Let g be a primitive root of o.

Euler's "Observationes circa divisionem quadratorum per numeros primos".

"Property of quadratic residues and non-residues of an odd prime number":

when each of these squares is divided by o to get their positive remainders (they are less than o) respectively, they are all the distinct quadratic residues ( is a quadratic residue of o, but is not used in here) of o. The integers: that are not included in the quadratic residues of o are all the distinct quadratic non-residues (the total number of them is: (o-1)/2) of o.

For h≥1, h-s≡-s(mod h).

Rule1: quadratic residue × quadratic residue=quadratic residue.

Rule2: quadratic residue × quadratic non-residue=quadratic non-residue.

Rule3: quadratic non-residue × quadratic non-residue=quadratic residue.

Law1: q-1 or -1 is a quadratic residue of q.

Law2: p-1 or -1 is a quadratic non-residue of p.

In Gauss's Disquisitiones Arithmeticae, articles 355 and 356, there are sine(from ancient Egypt) and cosine formulae with odd prime numbers.

Let be all the quadratic residues of o.

Let be all the quadratic non-residues of o.

are congruent respectively to the quadratic residues of o relative to modulus o, while are congruent respectively to the quadratic non-residues of o relative to modulus o.

m=(o-1)/2.

---(A)

When d≥1 and t=0,1,...,d-1: the roots of equation(A) are: cos(2πt/d)+sin(2πt/d), which is a known formula from Cotes's theorem.

---(B)

When d is odd and ≥3, the roots of equation(B) are: cos(2πt/d)+sin(2πt/d), where t=1,2,...,(d-1)/2,d-(d-1)/2,...,d-2,d-1. Since sin(θ)=0 only if θ=0,π,2π,3π,...,etc., the equation has only imaginary roots.

Set z be a root of equation(B) when d=o.

When 1≤u≤o-1: are all the distinct roots of equation(B) when d=o, this have been proved by Lagrange in his works on theory of equations.

When o-1=fb, define: while the collection of these f roots is called the period (f,c).

The collection of all the roots of equation(B) when d=o is consisted of the two periods (m,1) and (m,g).

Proof of the above statement can be found in Disquisitiones Arithmeticae section VII.

With Vieta's formulas by using (m,1) and (m,g) as the two roots, the following quadratic equation are formed:

---(C)

(m,1)+(m,g)=-1. ---(0.1)

Remark0: With Vieta's formulas, when d is odd and ≥3, sum of all the roots of equation(B) is= -1 can be verified by comparing the sum with the coefficient of in equation(B).

When o≡1(mod 4): (m,1)(m,g)=-m/2. ---(1.1)

When o≡3(mod 4): (m,1)(m,g)=(m+1)/2. ---(1.2)

Proof of formulae (1.1) and (1.2) can be found in Disquisitiones Arithmeticae section VII.

Solving the two roots of equation(C) with quadratic formula(from Mesopotamia), the values of (m,1) and (m,g) are:

when when

When ---(2.1)

When ---(2.2)

Formulae(3.1) and (3.2) are deduced from formula(2.1) while formulae(3.3) and (3.4) are deduced from formula(2.2).

When o≡3(mod 4):

sin(2πt/o)-sin(2πt/o)=. ---(3.1)

cos(2πt/o)-cos(2πt/o)=0. ---(3.2)

When o≡1(mod 4):

cos(2πt/o)-cos(2πt/o)=. ---(3.3)

sin(2πt/o)-sin(2πt/o)=0. ---(3.4)

Disquisitiones Arithmeticae:

Article 361.

With cos(2π+θ)=cos(θ) and cos(-θ)=cos(θ), we get:

Lemma0: For h≥1, cos(2π(h-s)/h)=cos(2πs/h).

With sin(2π+θ)=sin(θ) and sin(-θ)=-sin(θ), we get:

Lemma1: For h≥1, sin(2π(h-s)/h)=-sin(2πs/h).

Article 363.

With sin(θ±2πj)=sin(θ), cos(θ±2πj)=cos(θ), we get:

Footnote1: For h≥1, sin(2π(s±jh)/h)=sin(2πs/h), cos(2π(s±jh)/h)=cos(2πs/h).

Now, an application.

"Structures of quadratic residues and non-residues of q":

When o=q: with rule1 and law1,

all the quadratic residues of q are:

Proof: (q-1)/2 is an even number. Firstly, we find a quadratic residue (for example: 1) of q, then we will have the quadratic residue , secondly, we find a quadratic residue which is different from and , then we will have the quadratic residue , continue this process, until we get all the (q-1)/2 quadratic residues of q.

When o=q: with rule2 and law1,

all the quadratic non-residues of q are:

Proof: This is similar to that of the quadratic residues of q.

When o=p: with rule3 and law2, and with "Property of quadratic residues and non-residues of an odd prime number", we get:

Lemma2: are different with one another and are less than p and are all the quadratic residues of p. Since , we also get: are different with one another and are less than p and are all the quadratic non-residues of p.

With lemma2, =the corresponding quadratic non-residue of . With lemma0, cos(2π()/p)=cos(2π/p), we get:

Lemma3: Each quadratic residue of p and the corresponding quadratic non-residue are the same in the cos function with the multiplier, 2π/p. Also, with lemma2, =the corresponding quadratic residue of , we get: Each quadratic non-residue of p and the corresponding quadratic residue are the same in the cos function with the multiplier, 2π/p.

With lemma2, =the corresponding quadratic non-residue of . With lemma1, sin(2π()/p)=-sin(2π/p), we get:

Lemma4: Each quadratic residue of p and the corresponding quadratic non-residue have the same resulting value but with opposite sign in the sin function with the multiplier, 2π/p. Also, With lemma2, =the corresponding quadratic residue of , we get: Each quadratic non-residue of p and the corresponding quadratic residue have the same resulting value but with opposite sign in the sin function with the multiplier, 2π/p.

Lemma5: With lemma0, when d is odd and ≥3, we get: cos(2π((d-1)/2-a)/d)=cos(2π((d-1)/2+1+a)/d), where (d-1)/2-1≥a≥0. Therefore, when (d-1)/2-1≥a+1≥1, (d-1)/2-(a+1) and (d-1)/2+(a+1) can be treated as two consecutive integers (within 1 to (d-1)/2) when they are used separately in two cos functions with the multiplier 2π/d. When d≡1(mod 4) and ≥9: For (d-1)/4≥a+1≥2, (d-1)/2-(a+1),(d-1)/2+(a+1),(d-1)/2-1+(a+1),(d-1)/2-2+(a+1),...,(d-1)/2-a+(a+1), can be treated as consecutive integers when they are used separately in cos functions with the multiplier 2π/d. For (d-1)/2-2≥a+1≥(d-1)/4+1, (d-1)/2-(a+1),(d-1)/2+(a+1),(d-1)/2-1+(a+1),(d-1)/2-2+(a+1),...,(d-1)/2-((d-1)/2-(a+2))+(a+1), can be treated as consecutive integers when they are used separately in cos functions with the multiplier 2π/d.

Theorem0: Chinese square formula(明.胡居仁著 《易像鈔》"四象珓圖") from I Ching: hh=the total number of all the 2 symbols permutations with which the symbols are selected from h distinct symbols. For example, from the 2 symbols: † and ‡, all the 2 symbols permutations are: {††, †‡, ‡†, ‡‡}, the total number of 2 symbols permutations is=4=2⋅2.

From the symmetry of the 2 symbols permutations produced by theorem0, we get:

Corollary0: Each of the 2 symbols permutations produced by theorem0 has a corresponding reversed permutation, that is the position of the first symbol and last symbol in a 2 symbols permutation is exchanged. For example, the reversed permutation of †‡ is ‡†, the reversed permutation of †† is ††.

With remark0, the sum of imaginary parts of all the roots of equation(B) is=0 when d is odd and ≥3, so we get:

sin(2πk/d)=0 when d is odd and ≥3. ---(*)

cos(2πk/d)=-1 when d is odd and ≥3. ---(**)

With lemma0, formula(**) becomes:

2cos(2πk/d)=-1 when d is odd and ≥3. ---(***)

For formula(3.1), when t is a quadratic residue of p, with rule1 and rule2 and the theorem in article 23 of Disquisitiones Arithmeticae, we get:

sin(2π/p)-sin(2π/p)=.

Apply lemma4 to the second ∑ term of the above formula, it becomes:

2sin(2π/p)=. ---(I)

For formula(3.1), when t is a quadratic non-residue of p, with rule2 and rule3 and the theorem in article 23 of Disquisitiones Arithmeticae, we get:

-(sin(2π/p)-sin(2π/p))=.

From Euler's "Vollstandige Anleitung zur Algebra" part I section II chapters X and XI, we know that, (A+B+C+...+etc.)(A+B+C+...+etc.)=sum of all the permutations of the symbols: A, B, C, ...,etc., grouped by two. For example, (A+B)(A+B)=AA+AB+BA+BB.

Square of formula(I)=p=4 × sum of all the permutations of sin(2π/p) and sin(2π/p),

this sum consists of the terms, (sin(2π/p)) when i=j,

and when p is greater than 3, also the terms , 2sin(2π/p)sin(2π/p) when i≠j(as a result of Corollary0). The total number of the terms 2sin(2π/p)sin(2π/p) when i≠j is= the total number of combinations(from Lilavati) as 2 distinct symbols are selected from (p-1)/2 distinct symbols

"Procedure to list all the sums of two distinct even powers of primitive root of o≥5":

Step(1): Add 1 to respectively to form the sums. Step(2): Add to respectively to form the sums. Step(3): Add to respectively to form the sums. ... Until step(m-1): Add to to form the sum.

Note0: When o=p≥7: (mod p), where l=1,2,...,(m-1)/2, with this and the theorem in Disquisitiones Arithmeticae article 6, we get:

When o=p≥7: (mod p), where l=1,2,...,(m-1)/2.

Note1: When o=p≥7: each of these sums is not≡0(mod p) because of law2.

Note2: When o≥5: each of these differences is not≡0(mod o) since the only even power of primitive root of o which is≡1(mod o) is or .

With footnote1, when the original integer(for example: a quadratic residue of o) is congruent to an integer(for example: the corresponding even power of primitive root of o) relative to modulus o, this integer can be used instead of the original integer in the sin or cos function with the multiplier 2π/o to produce the same value.

To prove that sum of all the terms 2sin(2π/p)sin(2π/p) is=0 when i≠j:

We know cos(α-β)-cos(α+β)=2sin(α)sin(β). (trigonometric identities)

With footnote1, when o=p=7, we have the following transformations:

cos(2π()/7)-cos(2π()/7)=2sin(2π/7)sin(2π⋅1/7),

cos(2π()/7)-cos(2π()/7)=2sin(2π/7)sin(2π⋅1/7),

cos(2π()/7)-cos(2π()/7)=2sin(2π/7)sin(2π/7).

We have to show that sum of all the above differences of cos() is equal to 0.

We list all the sums of two distinct even powers of primitive root of o=p=7:

But with note0, (mod 7), so the list becomes:

These sums of two distinct even powers of primitive of 7 are noncongruent with one another(it can be proved by note1 and the theorem in article 23 of Disquisitiones Arithmeticae) relative to modulus 7. With rule1, when is a quadratic residue, these sums of two even powers of primitive will all be quadratic residues. With rule2, when is a quadratic non-residue, these sums of two even powers of primitive will all be quadratic non-residues.

We list all the sums of two distinct even powers of primitive root of o=p=11:

But with note0, (mod 11), so the list becomes:

These sums of two even powers of primitive root can be separated into 2 sets: set1 contains the sums with the factor set2 contains the sums with the factor

The sums in set1 (and so are the sums in set2) are noncongruent with one another(it can be proved by note1 and the theorem in article 23 of Disquisitiones Arithmeticae) relative to modulus 11. With rule1, when is a quadratic residue, the sums in set1 will all be quadratic residues. With rule2, when is a quadratic non-residue, the sums in set1 will all be quadratic non-residues. The same thing will happen for the sums in set2 as depended on whether is a quadratic residue or quadratic non-residue.

Note3: With lemma3, set of quadratic residues of p or set of quadratic non-residues of p is the same when all the quadratic residues or all the quadratic non-residues are used separately in the cos functions with the multiplier 2π/p.

Refer to "Procedure to list all the sums of two distinct even powers of primitive root of o≥5", we have the following observations:

1) The total number of sums produced in step(1) is=m-1, and each of the following steps will produced one fewer sum than that of the preceding step. Remember there are m-1 steps. For example, see the above list of all the sums of two distinct even powers of primitive root of o=p=7.

2) For o=p≥7, m-1 is an even number, for step(1), with note0, the first sum and the last sum have the same factor , the second sum and the second-last sum have the same factor ,..., the ((m-1)/2)th sum and the ((m-1)/2)th-last sum have the same factor . Remember there are m-1 sums in step(1). For example, see the first row in the above list of all the sums of two distinct even powers of primitive root of o=p=11.

3) The sums produced in step(2) are the same as that by removing the last sum produced in step(1) and then multiplying to the remaining sums in step(1). The sums produced in step(3) are the same as that by removing the last two sums produced in step(1) and then multiplying to the remaining sums in step(1). ... The sum produced in step(m-1) are the same as that by removing the last m-2 sums produced in step(1) and then multiplying to the remaining sum in step(1). For example, see the above list of all the sums of two distinct even powers of primitive root of o=p=7.

For o=p≥7, firstly, all the sums of two distinct even powers of primitive root of p will form a set of quadratic residues or quadratic non-residues with factor because with observations 3) and 1), we have the m-1 sums: from step(1) to step(m-1) respectively. With observation 2), we have one more sum: from step(1). With observations 1) and 3), we have no more sum from other steps for the factor with the condition in observation 2). Secondly, with observation 2), when (m-1)/2≥2, all the sums of two distinct even powers of primitive root will also form a set of quadratic residues or quadratic non-residues with factor because with observations 3) and 1), we have the m-2 sums: from step(1) to step(m-2) respectively. With observations 2) and 3), we have one more sum: from step(1) and one more sum: from step(2). With observations 1) and 3), we have no more sum from other steps for the factor with the condition in observation 2). Continue this process with next factor, until lastly, all the sums of two distinct even powers of primitive root will also form a set of quadratic residues or quadratic non-residues with factor because with observations 3) and 1), we have the m-(m-1)/2 sums: from step(1) to step(m-(m-1)/2) respectively. With observations 2) and 3), we have one more sum from each of the from step(1) to step((m-1)/2) respectively. With observations 1) and 3), we have no more sum from other steps for the factor with the condition in observation 2). So we have:

Theorem1: All the sums of two distinct quadratic residues of o=p≥7 is congruent to (m-1)/2 sets of quadratic residues or quadratic non-residues relative to modulus o, with which each of the sets has m quadratic residues or quadratic non-residues.

To list all the differences of two distinct even powers of primitive root of o≥5, we can use the "Procedure to list all the sums of two distinct even powers of primitive root of o≥5" by changing: "add 1 to" to "subtract 1 from", and by changing: "add to" to "subtract from",..., "add to" to "subtract from". So, all the differences of two distinct even powers of primitive root of o will have the same structure as that of all the sums of two distinct even powers of primitive root of o.

For example, we list all the differences of two distinct even powers of primitive root of o=p=7:

But with note0, (mod 7), so the list becomes:

With cos(-θ)=cos(θ), is the same as when being used in a cos function, so these differences of two distinct even powers of primitive (when being used in a cos function) of 7 are noncongruent with one another(it can be proved by note2 and the theorem in article 23 of Disquisitiones Arithmeticae) relative to modulus 7. This is true for all o=p≥7. Therefore, all the differences of two distinct even powers of primitive root (when being used in the cos function with the multiplier 2π/p) of o=p≥7 will form sets of quadratic residues or quadratic non-residues. With this and theorem1 and note3, we finish the proof of:

Theorem2: The sum of all the terms 2sin(2π/p)sin(2π/p) is=0 when i≠j.

With theorem2, square of formula(I) gives:

4(sin(2π/p))=p. ---(II)

With lemma4, when , -sin(2π/p)=sin(2π/p), and when is greater than (p-1)/2, is less than or equal to (p-1)/2, and with "Property of quadratic residues and non-residues of an odd prime number", formula(II) can be simplified to:

4(sin(2πk/p))=p. ---(III)

With "Structures of quadratic residues and non-residues of q" and observing the sizes of , we deduce that half of the integers: 1,2,...,(q-1)/2 are quadratic residues of q, and half of the integers: 1,2,...,(q-1)/2 are quadratic non-residues of q.

Square of formula(***)=1=4 × sum of all the permutations of cos(2πi/d) and cos(2πj/d), where i,j=1,2,...,(d-1)/2, this sum consists of the terms, (cos(2πi/d)) when i=j, and when d≥5, also the terms, 2cos(2πi/d)cos(2πj/d) when i≠j(as a result of Corollary0). The total number of the terms 2cos(2πi/d)cos(2πj/d) when i≠j is= the total number of combinations as 2 distinct symbols are selected from (d-1)/2 distinct symbols As all the terms 2cos(2πi/d)cos(2πj/d) when i≠j are transformed by, cos(α-β)+cos(α+β)=2cos(α)cos(β), it will produce ((d-1)/2)((d-1)/2-1) cos terms.

We list all the differences and sums of i and j in the cos terms produced by the transformations when d≡1(mod 4) and ≥5, they are:

(d-1)/2-((d-1)/2-1); (d-1)/2+(d-1)/2-1,

and for d≡1(mod 4) and ≥9, also the followings:

(d-1)/2-1-((d-1)/2-2), (d-1)/2-((d-1)/2-2); (d-1)/2+(d-1)/2-2, (d-1)/2-1+(d-1)/2-2,

...,

3-2, 4-2,..., (d-1)/2-2; (d-1)/2+2 ,...,4+2 ,3+2,

2-1, 3-1,..., (d-1)/2-1; (d-1)/2+1 ,...,3+1, 2+1.

In the above list of differences and sums of i and j, we call the first row as row(1), the second row as row(2),..., the last row as row((d-1)/2-1). Remember that the total number of sums = the total number of differences in each of the rows. Row((d-1)/4) is the middle row in the above list.

Note4: In the above list of differences and sums of i and j, the difference in row(1) is: 1; the differences in row(2) are: 1,2; ...; the differences in row((d-1)/2-1) are: 1,2,...,(d-1)/2-1. The sum in row(1) = add 2((d-1)/2-1) to the difference in row(1); the sums in row(2) = add 2((d-1)/2-2) to each of the differences in row(2);...; the sums in row((d-1)/2-1) = add 2⋅1 to each of the differences in row((d-1)/2-1).

We now show that in the above list of differences and sums of i and j, these differences and sums can be collected as (d-1)/2-1 sets of integers with which each set={1,2,...,(d-1)/2}. We use note4 in the following deduction.

Firstly, apply lemma5 to the difference and the sum in row(1), then collect all the integers in row(1), we get the set of integers: {1,2}; apply lemma5 to the difference: (d-1)/2-1 and the sum: (d-1)/2+1 in row((d-1)/2-1) and combine them with the remaining (d-1)/2-2 differences in row((d-1)/2-1), we get the set of integers: {1,2,...,(d-1)/2}; then combine all the integers in row(1) and row((d-1)/2-1), we get two {1,2,...,(d-1)/2}.

Secondly, apply lemma5 to the difference: (d-1)/2-((d-1)/2-2) and the sum: (d-1)/2+(d-1)/2-2 in row(2), then collect all the integers in row(2), we get the set of integers: {1,2,3,4}; apply lemma5 to the difference: (d-1)/2-2 and the sum: (d-1)/2+2 in row((d-1)/2-2) and combine them with the sum: (d-1)/2+1 and the remaining (d-1)/2-3 differences in row((d-1)/2-2), we get the set of integers: {1,2,...,(d-1)/2}; then combine all the integers in row(2) and row((d-1)/2-2), we get two {1,2,...,(d-1)/2}.

Continue the above process until the middle row is reached. Next apply lemma5 to the difference: (d-1)/2-(d-1)/4 and the sum: (d-1)/2+(d-1)/4 in row((d-1)/4), then collect all the integers in row((d-1)/4), we get the set of integers: {1,2,...,(d-1)/2}.

Finally we get ((d-1)/4-1)2+1 sets of {1,2,...,(d-1)/2}, with formula(***), we get ((d-1)/2-1)(-1/2), so we get:

Square of formula(***)=1=4(((d-1)/2-1)(-1/2)+(cos(2πk/d))) for d≡1(mod 4) and ≥9, we get:

4(cos(2πk/d))=d-2 for d≡1(mod 4) and ≥9. ---(V)

When d=5, square of formula(***)=1=4((cos(1⋅2π/5))+2cos(1⋅2π/5)cos(2⋅2π/5)+(cos(2⋅2π/5))), 2cos(2⋅2π/5)cos(1⋅2π/5)=cos((2-1)2π/5)+cos((2+1)2π/5), apply lemma5 to the difference: 2-1 and the sum: 2+1, we get the set of integers: {1,2}, so we get:

4((cos(1⋅2π/5))+(cos(2⋅2π/5)))=5-2. ---(VI)

Combine formulae(V) and (VI), and with (sin(θ))+(cos(θ))=1, we get:

4(sin(2πk/d))=d for d≡1(mod 4) and ≥5. ---(VII)

Since a positive integer divided by 4 will have a remainder of 0 or 1 or 2 or 3, any odd prime number is equal to either p or q. Also q≡1(mod 4) and ≥5. So we can combine formulae(III) and (VII) to get:

4(sin(2πk/o))=o. ---(VIII)

In Disquisitiones Arithmeticae article 337, there is an equation of degree w (when w is odd) whose roots are the sines with angles 2πt/w, where t=0,1,...,w-1. With Newton's identities and the coefficients of the equation, we can get a formula of sum of squares of sine similar to formula(VIII).

Examples:

For formula(*):

sin(1⋅2π/3)+sin(2⋅2π/3)=0.

sin(1⋅2π/5)+sin(2⋅2π/5)+sin(3⋅2π/5)+sin(4⋅2π/5)=0.

For formula(***):

2cos(1⋅2π/3)=-1.

2(cos(1⋅2π/5)+cos(2⋅2π/5))=-1.

For formula(VIII):

4(sin(1⋅2π/3))=3.

4((sin(1⋅2π/5))+(sin(2⋅2π/5)))=5.

4((sin(1⋅2π/7))+(sin(2⋅2π/7))+(sin(3⋅2π/7)))=7.

References

[1]

References

  1. ^ Gauss's Disquisitiones Arithmeticae