# Fourier Transform over Finite Abelian Groups

Here is an overview of Fourier analysis applied to finite abelian groups. It shows how to generalize a priori different computations such as the discrete Fourier transform or the Hadamard-Walsh transform.

CHARACTER

Let $G$ be a finite abelian group with additive notation. A character of $G$ is a group homomorphism $\chi : G \rightarrow \mathbb{C} - \{ 0 \}$ that is to say for all $a , b \in G$

$\displaystyle \chi ( a + b ) = \chi ( a ) \chi ( b )$

$\displaystyle \chi ( 0 ) = 1$

# Nonlinear Pendulum

A simple pendulum consists of a single point of mass $m$ attached to a rod of length $l$ and of negligible weight. We denote by $\theta$ the angle measured between the rod and the vertical axis. By applying the Newton’s law of dynamics we obtain the equation of motion

$\displaystyle m l^2 \ddot{\theta} + m g l \sin \theta = 0$

It can be simplified by putting $\omega = \sqrt{g / l}$

$\displaystyle \ddot{\theta} + \omega^2 \sin \theta = 0$

We simplify the equations by normalizing $\omega = 1$ without loss of generality.

$\displaystyle \ddot{\theta} + \sin \theta = 0$

# Derivation in Algebra

It is well known that the derivative is an operation on functions which is linear

$\displaystyle \begin{array}{c} \left(f+g\right)'=f'+g'\\ \left(\lambda f\right)'=\lambda f'\end{array}$

and satisfies the Leibniz rule

$\displaystyle \left(fg\right)'=f'g+fg'$

In fact, these two properties are purely algebraic and can be generalized with no reference to infinitesimal calculus. This approach has become common in modern mathematics since it allows profitable interactions between multiples domains such as algebra, analysis and geometry.

# Morley’s Theorem, Alain Connes’s Proof

At the end of 19th century, the British mathematician Frank Morley discovered the following surprising property :

The three points of intersection of the adjacent trisectors of the angles of any triangle are the vertices of an equilateral triangle.

There are many proofs of this result, but one of them given by Alain Connes is especially beautiful and interesting as a group theoretic property of the action of the affine group on the line. We propose an overview of his proof.

# CORDIC Algorithm

Unlike a common belief, most calculators do not use Taylor series to compute trigonometric functions, but the much more efficient CORDIC algorithm, namely COordinate Rotation DIgital Computer. It was developed by Volder in 1959 although the ideas can already be found in the work of Briggs in the XVIIth century.

How to efficiently approximate $\tan \theta \textrm{ for } \theta \in [ 0 ; \frac{\pi}{2}[$ ? Continue reading

# Binary GCD

ALGORITHM

It is well known that the Euclidean algorithm for the greatest common divisor can be expressed by the recursive formula

$\gcd ( U , V ) = \gcd ( V , U \mod V )$

Another algorithm, published by Stein in 1967, uses only multiplication and division by 2. It can be described as follows

1. If U and V are both even, then $\gcd(U,V) = 2 \gcd(U/2,V/2)$
2. If U is even and V is odd, then $\gcd(U,V) = \gcd(U/2,V)$
3. If U is odd and V is even, then $\gcd(U,V) = \gcd(U,V/2)$
4. If U and V are both odd, then $\gcd(U,V) = \gcd(|U-V|/2,\min(U,V))$

# Division by increasing power order

Euclid conducting a proof (Raphael's fresco School Of Athens, 1511)

The division of polynomials by increasing power order is similar to the usual Euclidean division but in reversed order : the terms of lower degree of the dividend are eliminated first. Some useful algorithms can be deduced from this process, such as series expansion or partial fraction decomposition.

EUCLIDEAN DIVISION

It is well known that given two polynomials $A$ and $B \neq 0$ on a commutative field K, it is always possible to perform the Euclidean division

$\displaystyle A = B Q + R , \deg(R)<\deg(B)$