Fourier transform of a Fourier series

Posted on by John

The previous post showed how we can take the Fourier transform of functions that don’t have a Fourier transform in the classical sense.

The classical definition of the Fourier transform of a function f requires the integral of |f| over the real line to be finite. This implies f(x) must approach zero as x goes to ∞ and −∞. A constant function won’t do, and yet we got around that in the previous post. Distribution theory even lets you take the Fourier transform of functions that grow as their arguments go off to infinity, as long as they don’t grow too fast, i.e. like a polynomial but not like an exponential.

In this post we want to take the Fourier transform of functions like sine and cosine. If you read that sentence as saying Fourier series, you have the right instinct for classical analysis: you take the Fourier series of periodic functions, not the Fourier transform. But with distribution theory you can take the Fourier transform, unifying Fourier series and Fourier transforms.

For this post I’ll be defining the classical Fourier transform using the convention

{\cal F} \{ f(x) \}(\omega) = \hat{f}(\omega) = \int_{-\infty}^\infty \exp(-2\pi i \omega x)\, f(x)\, dx

and generalizing this definition to distributions as in the previous post.

With this convention, the Fourier transform of 1 is δ, and the Fourier transform of δ is 2π.

One can show that the Fourier transform of a cosine is a sum of delta functions, and the Fourier transform of a sine is a difference of delta functions.

\begin{align*} {\cal F} \{\cos 2\pi a x\} &= \frac{1}{2}\left(\delta(\omega - a) + \delta(\omega + a) \right) \\ {\cal F} \{\sin 2\pi a x\} &= \frac{1}{2i}\left(\delta(\omega - a) - \delta(\omega + a) \right) \end{align*}

It follows that the Fourier transform of a Fourier series is a sum of delta functions shifted by integers. In fact, if you convert the Fourier series to complex form, the coefficients of the deltas are exactly the Fourier series coefficients.

{\cal F}\left\{ \sum_{n=-\infty}^\infty c_n \exp(2\pi i n x) \right\} = \sum_{n=-\infty}^\infty c_n \delta(\omega - n)

Related posts

Fourier transform of a flat line

Posted on by John

Suppose you have a constant function f(x) = c. What is the Fourier transform of f?

We will show why the direct approach doesn’t work, give two hand-wavy approaches, and a rigorous definition.

Direct approach

Unfortunately there are multiple conventions for defining the Fourier transform.

For this post, we will define the Fourier transform of a function f to be

\hat{f}(\omega) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^\infty \exp(-i \omega x)\, f(x)\, dx

If f(x) = c then the integral diverges unless c = 0.

Heuristic approach

The more concentrated a function is in the time domain, the more it spreads out in the frequency domain. And the more spread out a function is in the time domain, the more concentrated it is in the frequency domain. If you think this sounds like the Heisenberg uncertainty principle, you’re right: there is a connection.

A constant function is as spread out as possible, so it seems that its Fourier transform should be as concentrated as possible, i.e. a delta function. The delta function isn’t literally a function, but it can be made rigorous. More on that below.

Gaussian density approach

The Fourier transform of the Gaussian function exp(−x²/2) is the same function, i.e. the Gaussian function is a fixed point of the Fourier transform. More generally, the Fourier transform of the density function for a normal random variable with standard deviation σ is the density function for a normal random variable with standard deviation 1/σ.

As σ gets larger, the density becomes flatter. So we could think of our function f(x) = c as some multiple of a Gaussian density in the limit as σ goes to infinity. The Fourier transform is then some multiple of a Gaussian density with σ = 0, i.e. a point mass or delta function.

Rigorous approach

If f and φ are two well-behaved functions then

\int_{-\infty}^\infty \hat{f}(x) \, \varphi(x) \,dx = \int_{-\infty}^\infty f(x) \, \hat{\varphi}(x) \,dx

In other words, we can move the “hat” representing the Fourier transform from one function to the other. The equation above is a theorem when f and φ are nice functions. We can use it to motivate a definition when the function f is not so nice but the function φ is very nice. Specifically, we will assume φ is an infinitely differentiable function that goes to zero at infinity faster than any polynomial.

Given a Lebesgue integrable function f, we can think of f as a linear operator via the map

\varphi \mapsto \int_{-\infty}^\infty f(x) \, \varphi(x) \, dx

More generally, we can define a distribution to be any continuous [1] linear operator from the space of test functions to the complex numbers. A distribution that can be defined by integral as above is called a regular distribution. When we say we’re taking the Fourier transform of the constant function f(x) = c,  we’re actually taking the Fourier transform of the regular distribution associated with f. [2]

Not all distributions are regular. The delta “function” δ(x) is a distribution that acts on test functions by evaluating them at 0.

\delta: \varphi \mapsto \varphi(0)

We define the Fourier transform of (the regular distribution associated with) a function f to be the distribution whose action on a test function φ equals the integral of the product of f and the Fourier transform of φ. When a function is Lebesgue integrable, this definition matches the classical definition.

With this definition, we can calculate that the Fourier transform of a constant function c equals

\sqrt{2 \pi} \, c\, \delta

Note that with a different convention for defining the Fourier transform, you might get 2π c δ or just c δ.

An advantage of the convention that we’re using is that the Fourier transform of the Fourier transform of f(x) is f(−x) and not some multiple of f(−x). This implies that the Fourier transform of √2π δ is 1 and so the Fourier transform of δ is 1/√2π.

Related posts

[1] To define continuity we need to put a topology on the space of test functions. That’s too much for this post.

[2] The constant function doesn’t have a finite integral, but its product with a test function does because test functions decay rapidly. In fact, even the product of a polynomial with a test function is integrable

Obscuring P2P nodes with Dandelion

Posted on by John

The weakest link in the privacy of cryptocurrency transactions is often outside the blockchain. There are technologies such as stealth addresses and subaddresses to try to thwart attempts to link transactions to individuals. They do a good job of anonymizing transaction data, but the weak link may be metadata, as is often the case.

Cryptocurrency nodes circulate transaction data using a peer-to-peer network. An entity running multiple nodes can compare when data arrived at each of its nodes and triangulate to infer which node first sent a set of transactions. The Dandelion protocol, and its refinement Dandelion++, aims to mitigate this risk. Dandelion++ is currently used in Monero and a few other coins; other cryptocurrencies have considered or are considering using it.

Dandelion plant

The idea behind the Dandelion protocol is to have a “stalk” period and a “diffusion” period. Imagine data working up the stalk of a dandelion plant before diffusing like seeds in the wind. The usual P2P process is analogous to simply blowing on the seed head [1].

During the stalk period, information travels from one node to one node. Then after some number of hops, the diffusion process begins; the final node in the stalk period diffuses the information to all its peers. An observer with substantial but not complete visibility of the network may be able to determine which node initiated the diffusion, but maybe not the node at the other end of the stem.

A natural question is how this differs from something like Tor. In a nutshell, Tor offers identity protection before you enter a P2P network, and Dandelion offers identity protection inside the P2P network.

For more details, see the original paper on Dandelion [2].

Related posts

[1] The original paper on Dandelion uses a dandelion seed as the metaphor for the protocol. “The name ‘dandelion spreading’ reflects the spreading pattern’s resemblance to a dandelion seed head and refers to the diagram below. However, other sources refer to the stalk and head of the dandelion plant, not just a single seed. Both mental images work since the plant has a slightly fractal structure with a single seed looking something like the plant.

Illustration from Dandelion protocol paper

[2] Shaileshh Bojja Venkatakrishnan, Giulia Fanti, Pramod Viswanath. Dandelion: Redesigning the Bitcoin Network for Anonymity. Proceedings of the ACM on Measurement and Analysis of Computing Systems, Volume 1, Issue 1 Article No.: 22, Pages 1–34. Available here: https://doi.org/10.1145/3084459.

What is a Pedersen commitment?

Posted on by John

I’m taking a break from my series on celestial navigation. The previous posts give the basics, but I haven’t thought of a way to go further that I’m satisfied with. So now for something completely different: Pedersen commitments.

Pedersen commitments are a building block of zero knowledge proofs (ZKP), and they give an opportunity to look at a couple other other interesting topics: nothing-up-my-sleeve constructions and homomorphic encryption.

A Pedersen commitment to a value v takes a random number x and two generators of an elliptic curve, G and H, and returns

C = vG + xH.

The significance of C is that it appears to be a random number to the recipient, but the sender who calculated it can later show that it was computed from v and x. C is called a commitment to the value v because the sender cannot later say that C was computed from a different v and a different x.

Mathematical details

The addition in

C = vG + xH

is carried out on on an elliptic curve, such as Ed25519 in the case of Monero. Multiplication is defined by repeated addition, though it’s not computed that way [1]. G and H are not just points on the elliptic curve but points in a large, prime-order subgroup of the elliptic curve.

Because the value x is random, the possible values of C are uniformly distributed on the curve, and so someone observing C learns nothing about v. For that reason x is called a blinding factor.

The difficulty of the discrete logarithm problem insures that it is impractical come up with different values v‘ and x‘ such that

v G + x H = v‘ G + x‘ H.

This depends on two assumptions.

The first assumption is that the discrete logarithm problem is hard to solve given current algorithms and hardware. The prevailing opinion is that it is unlikely anyone will come up with an efficient algorithm for solving the discrete logarithm problem on current hardware. However, Shor’s algorithm could solve the discrete logarithm problem efficiently if and when a practical, large-scale quantum computer is created.

The second assumption is that the generator H was chosen at random and not calculated to be a backdoor.

How to make and use a backdoor

Because G and H are members of the same prime-order (i.e. cyclic) group, there exists some integer h such

H = hG

If the generator H was randomly selected, nobody knows h and nobody can calculate it. But if H was calculated by first selecting h and multiplying hG then there is a backdoor.

Now

C = vG + xH = vG + x(hG) = (v + xh)G.

If you know h, you can pick a new v‘ and solve for x‘ such that

v + xh = v‘ + x‘ h.

That would mean that in the context of a cryptocurrency that uses Pedersen commitments, such as Monero or the Liquid Network on top of Bitcoin, you could initially commit to spending v and later claimed that you committed to spending v‘.

Note that solving for x‘ requires modular arithmetic, not solving the discrete logarithm problem.

How to prove no backdoor

The way to prove that the generator H was chosen in good faith is to be transparent about how it was created. In practice this means using some sort of cryptographic hash function. For example, Bulletproofs hashed “bulletproof_g” and “bulletproof_h” to create its values of G and H. Bulletproofs require multiple values of G and H and so consecutive integers were concatenated to the strings before hashing.

Reversing a cryptographic hash like SHA256 is impractical, even assuming you have a quantum computer, and so it is extremely unlikely that there is a backdoor when the generators were created by hashing a natural string.

It’s said that Pedersen commitments do not require a trusted setup. That’s true in spirit, but more precisely they require a transparent setup that is easy to trust.

Homomorphic encryption

The function

C: (v, x) ↦ vG + xH

is a group homomorphism from pairs of integers to the subgroup generated by G and H. This means that

C(v, x) + C(v‘, x‘) = C(v + v‘, x + x‘)

or in other words, you can combine multiple commitments into a single commitment. The sum of a commitment to (v, x) and a commitment to (v‘, x‘) is a commitment to (v + v‘, x + x‘).

Related posts

[1] In practice the number x is enormous, say on the order of the number of points on the elliptic curve, and so software does not add H to itself x times. Instead it uses a process analogous to fast exponentiation. In fact, if you write the group operation multiplicatively rather than addititively, it is exactly fast exponentiation.

Solving spherical triangles

Posted on by John

This post is a side quest in the series on navigating by the stars. It expands on a footnote in the previous post.

There are six pieces of information associated with a spherical triangle: three sides and three angles. I said in the previous post that given three out of these six quantities you could solve for the other three. Then I dropped a footnote saying sometimes the missing quantities are uniquely determined but sometimes there are two solutions and you need more data to uniquely determine a solution.

Todhunter’s textbook on spherical trig gives a thorough account of how to solve spherical triangles under all possible cases. The first edition of the book came out in 1859. A group of volunteers typeset the book in TeX. Project Gutenberg hosts the PDF version of the book and the TeX source.

I don’t want to duplicate Todhunter’s work here. Instead, I want to summarize when solutions are or are not unique, and make comparisons with plane triangles along the way.

SSS and AAA

The easiest cases to describe are all sides or all angles. Given three sides of a spherical triangle (SSS), you can solve for the angles, as with a plane triangle. Also, given three angles (AAA) you can solve for the remaining sides of a spherical triangle, unlike a plane triangle.

SAS and SSA

When you’re given two sides and an angle, there is a unique solution if the angle is between the two sides (SAS), but there may be two solutions if the angle is opposite one of the sides (SSA). This is the same for spherical and plane triangles.

There could be even more than two solutions in the spherical case. Consider a triangle with one vertex at the North Pole and two vertices on the equator. Two sides are specified, running from the pole to the equator, and the angles at the equator are specified—both are right angles—but the side of the triangle on the equator could be any length.

ASA and AAS

When you’re given two angles and a side, there is a unique solution if the side is common to the two angles (ASA).

If the side is opposite one of the angles (AAS), there may be two solutions to a spherical triangle, but only one solution to a plane triangle. This is because two angles uniquely determine the third angle in a plane triangle, but not in a spherical triangle.

The example above of a triangle with one vertex at the pole and two on the equator also shows that an AAS problem could have a continuum of solutions.

Summary

\begin{tabular}{|l|c|c|} \hline \textbf{Case} & \textbf{Plane} & \textbf{Spherical} \\ \hline SSS & 1 & 1 \\ SAS & 1 & 1 \\ SSA & 1 or 2 & 1 or 2 \\ AAS & 1 & 1 or 2 \\ ASA & 1 & 1 \\ AAA & $\infty$ & 1 \\ \hline \end{tabular}

Note that spherical triangles have a symmetry that plane triangles don’t: the spherical column above remains unchanged if you swap S’s and A’s. This is an example of duality in spherical geometry.

The Navigational Triangle

Posted on by John

The previous post introduced the idea of finding your location by sighting a star. There is some point on Earth that is directly underneath the star at any point in time, and that location is called the star’s GP (geographic position). That is one vertex of the navigational triangle. The other two vertices are your position and the North Pole.

Unless you’re at Santa’s workshop and observing a star nearly directly overhead, the navigational triangle is a big triangle, so big that you need to use spherical geometry rather than plane geometry. We will assume the Earth is a sphere [1].

Let a be the side running from your position to the GP. In the terminology of the previous post a is the radius of the line of position (LOP).

Let b be the side running from the GP to the North Pole. This is the GP’s lo-latitude, the complement of latitude.

Let c be the side running from your location to the North Pole. This is your co-latitude.

Let A, B, and C be the angles opposite a, b, and c respectively. The angle A is known as the local hour angle (LHA) because it is proportional to the time difference between noon at your location and noon at the GP.

Given three items from the set {a, b, c, A, B, C} you can solve for the other three [2]. Note that one possibility is knowing the three angles. This is where spherical geometry differs from plane geometry: you can’t have spherical triangles that are similar but not congruent because the triangle excess determines the area.

If you know the current time, you can look up the GP coordinates in a table. The complement of the GP’s latitude is the side b.

Also from the current time you can determine your longitude, and from that you can find the LHA (angle A).

As described in the previous post, the altitude of the star, along with its GP, determines the LOP. From the LOP you can determine the arc between you and the GP, i.e. side a. We haven’t said how you could determine a, only that you could.

If you know two sides (in our case a and b) and the angle opposite one of the sides (in our case A) you can solve for the rest.

Adding detail

This post is more detailed than the previous, but still talks about what can be calculated but now how. We’re adding detail as the series progresses.

To motivate future posts, note that just because something can in theory be computed from an equation, that doesn’t mean it’s best to use that equation. Maybe the equation is sensitive to measurement error, or is numerically unstable, or is hard to calculate by hand.

Since we’re talking about navigating by the stars rather than GPS, we’re implicitly assuming that you’re using pencil and paper because for some reason you can’t use GPS.

Related posts

[1] To first approximation, the Earth is a sphere. To second approximation, it’s an oblate spheroid. If you want to get into even more detail, it’s not exactly an oblate spheroid. How much difference does all this make? See this post.

[2] In some cases there are two solutions for one of the missing elements and you’ll need to use additional information, such as your approximate location, to rule out one of the possibilities. More on when solutions are unique here.

Line of position (LOP)

Posted on by John

The previous post touched on how Lewis and Clark recorded celestial observations so that the data could be turned into coordinates after they returned from their expedition. I intend to write a series of posts about celestial navigation, and this post will discuss one fundamental topic: line of position (LOP).

Pick a star that you can observe [1]. At any particular time, there is exactly one point on the Earth’s surface directly under the star, the point where a line between the center of the Earth and the star crosses the Earth’s surface. This point is called the geographical position (GP) of the star.

This GP can be predicted and tabulated. If you happen to be standing at the GP, and know what time it is, these tables will tell your position. Most likely you’re not going to be standing directly under the star, and so it will appear to you as having some deviation from vertical. The star would appear at the same angle from vertical for ring of observers. This ring is called the line of position (LOP).

An LOP of radius 1200 miles centered at a GP at Honolulu

The LOP is a “small circle” in a technical sense. A great circle is the intersection of the Earth’s surface with a plane through the Earth’s center, like a line of longitude. A small circle is the intersection of the surface with a plane that does not pass through the center, like a line of latitude.

The LOP is a small circle only in contrast to a great circle. In fact, it’s typically quite large, so large that it matters that it’s not in the plane of the GP. You have to think of it as a slice through a globe, not a circle on a flat map, and therein lies some mathematical complication, a topic for future poss. The center of the LOP is the GP, and the radius of the LOP is an arc. This radius is measured along the Earth’s surface, not as the length of a tunnel.

One observation of a star reduces your set of possible locations to a circle. If you can observe two stars, or the same star at two different times, you know that you’re at the intersection of the two circles. These two circles will intersect in two points, but if you know roughly where you are, you can rule out one of these points and know you’re at the other one.

 

[1] At the time of the Lewis and Clark expedition, these were the stars of interest for navigation in the northern hemisphere: Antares, Altair, Regulus, Spica, Pollux, Aldeberan, Formalhaut, Alphe, Arieties, and Alpo Pegas. Source: Undaunted Courage, Chapter 9.

Lewis & Clark geolocation

Posted on by John

I read Undaunted Courage, Stephen Ambrose’s account of the Lewis and Clark expedition,  several years ago [1], and now I’m listening to it as an audio book. The first time I read the book I glossed over the accounts of the expedition’s celestial observations. Now I’m more curious about the details.

The most common way to determine one’s location from sextant measurements is Hilare’s method [2], developed in 1875. But the Lewis and Clark expedition took place between 1804 and 1806. So how did the expedition calculate geolocation from their astronomical measurements? In short, they didn’t. They collected data for others to turn into coordinates later. Ambrose explains

With the sextant, every few minutes he would measure the angular distance between the moon and the target star. The figures obtained could be compared with tables show how those distances appeared at the same clock time in Greenwich. Those tables were too heavy to carry on the expedition, and the work was too time-consuming. Since Lewis’s job was to make the observations and bring them home, he did not try to do the calculations; he and Clark just gathered the figures.

The question remains how someone back in civilization would have calculated coordinates from the observations when the expedition returned. This article by Robert N. Bergantino addresses this question in detail.

Calculating latitude from measurements of the sun was relatively simple. Longitude was more difficult to obtain, especially without an accurate way to measure time. The expedition had a chronometer, the most expensive piece of equipment on the expedition that was accurate enough to determine the relative time between observations, but not accurate enough to determine Greenwich time. A more accurate chronometer would have been too expensive and too fragile to carry on the voyage.

For more on calculating longitude, see Dava Sobel’s book Longitude.

Related posts

[1] At least 17 years ago. I don’t keep a log of what I read, but I mentioned Undaunted Courage in a blog post from 2008.

[2] More formally known as Marcq Saint-Hilaire’s intercept method.

Zero knowledge proof of compositeness

Posted on by John

A zero knowledge proof (ZKP) answers a question without revealing anything more than answer. For example, a digital signature proves your possession of a private key without revealing that key.

Here’s another example, one that’s more concrete than a digital signature. Suppose you have a deck of 52 cards, 13 of each of spades, hearts, diamonds, and clubs. If I draw a spade from the deck, I can prove that I drew a spade without showing which card I drew. If I show you that all the hearts, diamonds, and clubs are still in the deck, then you know that the missing card must be a spade.

Composite numbers

You can think of Fermat’s primality test as a zero knowledge proof. For example, I can convince you that the following number is composite without telling you what its factors are.

n = 244948974278317817239218684105179099697841253232749877148554952030873515325678914498692765804485233435199358326742674280590888061039570247306980857239550402418179621896817000856571932268313970451989041

Fermat’s little theorem says that if n is a prime and b is not a multiple of n, then

bn−1 = 1 (mod n).

A number b such that bn−1 ≠ 1 (mod n) is a proof that n is not prime, i.e. n is composite. So, for example, b = 2 is a proof that n above is composite. This can be verified very quickly using Python:

    >>> pow(2, n-1, n)
    10282 ... 4299

I tried the smallest possible base [1] and it worked. In general you may have to try a few bases. And for a few rare numbers (Carmichael numbers) you won’t be able to find a base. But if you do find a base b such that bn−1 is not congruent to 1 mod n, you know with certainty that n is composite.

Prime numbers

The converse of Fermat’s little theorem is false. It can be used to prove a number is not prime, but it cannot prove that a number is prime. But it can be used to show that a number is probably prime. (There’s some subtlety as to what it means for a number to probably be prime. See here.)

Fermat’s little theorem can give you a zero knowledge proof that a number is composite. Can it give you a zero knowledge proof that a number is prime? There are a couple oddities in this question.

First, what would it mean to have a zero knowledge proof that a number is prime? What knowledge are you keeping secret? When you prove that a number is composite, the prime factors are secret (or even unknown), but what’s the secret when you say a number is prime? Strictly speaking a ZKP doesn’t have to keep anything secret, but in practice it always does.

Second, what about the probability of error? Zero knowledge proofs do not have to be infallible. A ZKP can have some negligible probability of error, and usually do.

It’s not part of the definition, but practical ZKPs must be easier to verify than the direct approach to what they prove. So you could have something like a primality certificate that takes far less computation to verify than the computation needed to determine from scratch that a number is prime.

Proving other things

You could think of non-constructive proofs as ZKPs. For example, you could think of the intermediate value theorem as a ZKP: it proves that a function has a zero in an interval without giving you any information about where that zero may be located.

What makes ZKPs interesting in application is that they can prove things of more general interest than mathematical statements [2]. For example, cryptocurrencies can provide ZKPs that accounting constraints hold without revealing the inputs or outputs of the transaction. You could prove that nobody tried to spend a negative amount and that the sum of the inputs equals the sum of the outputs.

Related posts

[1] You could try b = 1, but then bn−1 is always 1. This example shows that the existence of a base for which bn−1 = 1 (mod n) doesn’t prove anything.

[2] You might object that accounting rules are mathematical statements, and of course they are. But they’re of little interest to mathematicians and of great interest to the parties in a transaction.

Monero subaddresses

Posted on by John

Monero has a way of generating new addresses analogous to the way HD wallets generate new addresses for Bitcoin. In both cases, the recipient’s software can generate new addresses to receive payments that others cannot link back to the recipient.

Monero users have two public/private keys pairs: one for viewing and one for spending. Let Ks and ks be the public and private spending keys, and let Kv and kv be the public and private viewing keys. Then the user’s ith subaddress is given by

\begin{align*} K^s_i &= K^s + H(k^v, i) G \\ K^v_i &= k^v K^s_i \end{align*}

Here G is a generator for the elliptic curve Ed25519 and H is a hash function. The hash function output and kv are integers; the public keys, denoted by capital Ks with subscripts and superscripts, are points on Ed25519. The corresponding private keys are

\begin{align*} k^s_i &= k^s + H(k^v, i) \\ k^v_i &= k^v + k^s_i \end{align*}

As with hierarchical wallets, the user scans the blockchain to see which of his addresses have received funds.

A user may choose to give a different subaddress for each transaction for added security, or to group transactions for accounting purposes.

Note that in addition to subaddresses, Monero uses stealth addresses. An important difference between subaddresses and stealth addresses is that recipients generate subaddresses, and senders generate stealth addresses. Someone could send you money to the same subaddress twice, failing to create a new stealth address. This is not possible if you give the sender a different subaddress each time.

Related posts