This blog is for those who are curious about how mathematics shapes our world. Some of the most powerful applications of mathematics come from the need to develop military technologies in which the lives of entire nations might be at stake. Here, necessity is truly the mother of invention. The atomic bomb for example, could not have been discovered without Albert Einstein’s famous equation, . Similarly, there would be no aircraft radar and naval sonar techniques without the help of math.

I want to tell the story sonar technology unfolded during the 1940’s. It’s a story that began rather improbably with Hollywood and finished with scientists deriving a beautiful “sonar equation” of great help to the navy.

Our story begins with Hedy Lamarr (1914 – 2000), a legend from the golden era of moving pictures. Unusual for an actress, Lemarr took an interest in solving engineering problems. In the 1940s, she was mulling over the problem how to control a torpedo by radio without being jammed by the enemy. Her brilliant answer: by frequency hopping – that is, synchronize both the torpedo transmitter and its receiver as they hop from frequency to frequency, thus confusing the enemy who doesn’t know which frequency to jam. Although Lemarr’s idea didn’t take off (the US Naval folks had another approach to the problem), she was hailed as a pioneer of modern communications technology, which is not far from the truth since all mobile phones today use a more advanced version of her frequency hopping idea. However, instead of hopping, signals are spread over several frequencies simultaneously.

Rather than avoiding jamming, the priority of the US navy was to develop a system to distinguish between reflected signals, so that both the distance to an object and its speed can be measured precisely. But there was a major problem, illustrated in figures 1 and 2 which are simplified frequency-time plots of echo reflections.

In Figure 1, the gray cells on the 6-by-6 grid represents a sequence of echo reflections from a stationary object. The chart on the right shows the sequence shifted in time (along the horizontal axis).

The problem facing the navy engineers is that it is not always possible to distinguish between a reflection shifted in time from that of a closer moving object shifted in frequency (along the vertical axis) as shown on the right-hand side of Figure 2.

For sonar to work precisely, the navy needed to focus on a particular frequency-time pattern that enables them to distinguish between various kinds of echo reflections and to read them with ease. This pattern would have the property that any two distinct shifts (horizontal or vertical or a combination of both) have at most one “ping” in common. Such a pattern is called a Costas Array, named American engineer, John P. Costa (1923 – 2008). The question is how to locate a Costas Array in real time. The solution calls for some mathematical thinking. For starters, we need to interpret a frequency-time pattern in the language of mathematics. Then, we have to derive an equation to pin down the coordinates of a Costas Array.

Note to readers: you can skip the math below and jump to the conclusion at the end. Or, (as I would recommend), follow the steps which are mostly based on concepts familiar from high school math.

Let’s proceed. If your device detects a frequency-time pattern like Figure 3 below, bingo – you have found a Costas Array!  You easily see that the pattern in this figure has the property that any two distinct shifts (vertical, or horizontal or a combination of both) have at most one “ping” in common.

The next task is to find an equation that exactly describes this pattern. We begin by interpreting a frequency-time pattern as a function:

(1)

defined over a short initial segment of natural numbers, say,

X = {1,2,….,n}

where for simplicity, n = 6 to mirror the plots. In Figure 3, the graph shifted b units to the right and a units in the vertical direction. The following function can be used to represent these shifts.

(2)

where at least one of the parameters a, b is different from zero.

For sonar precision, we want the function to have at most one solution. What kind of function satisfy this criterion? The answer, very simply, is a linear equation

(3)

Therefore, the idea is to make equation (2) to be equivalent to a linear equation after some rearrangements. How to do that is the problem. Since we want to solve equations involving the unknown function f, it would be nice if has an inverse function such that:

(4)

We can then apply g to both sides of equation (2) to get

(5)

It would be nice too, if this equation can be simplified into a linear equation. For this to happen, g must satisfy the identity: If we let g(1) = d, a constant, then this identify implies that g is an exponential function of the form:

(6) for all x in X.

At this point, we shall call upon some nifty mathematical tricks known as modular arithmetic. The idea is to reduce every result modulo some fixed integer, m.

(7)

The basics of modular arithmetic are explained in the end notes. For now, I’ll ask you to trust the results shown below. Since our Costa Array is a 6 x 6 grid, we want n = 6.  Look what happens when we let m = 7 and d = 3.

Behold! We get a running sequence of 6 numbers from 1 to 6, as desired. From high school algebra, recall that the opposite of exponentiation is logarithms (or logs in short). The following log operations to base 3 leads to the sequence 1, 2, …, 6.

You can almost see where we’re heading. With the dignified entrance of the log operation, we get the discrete logarithm function which produces the exact frequency-time pattern in Figure 3!

A final note: What we just did is a construction known as the Welch-Costa array. Our example can be easily generalized to a larger grid. Moreover, the equation works for every prime number p in place of the number 7.

Note: The ABCs of Modular Arithmetic

This note is a primer on modular arithmetic. Modular arithmetic is a special (if strange) type of arithmetic that involves only whole numbers or integers. While it may seem confusing at first, counting using this type of arithmetic helps mathematicians handle a large array of number theory problems more easily.

When we divide two integers, we have an equation that looks like:

A/B = Q + R, where

A is the dividend
B is the divisor
Q is the quotient
R is the remainder

Sometimes, we are only interested in what the remainder is when A is divided by B. For these cases, there is an operator called modulo operator (shorthand: mod).

For example, 13/5 gives a Q of 2 and R of 3 or “2 remainder 3”. Thus, we say that

13 mod 5 = 2

For a given mod, m, the remainder starts with 0, increases by one as the dividend increases by one until it reaches m-1. Then it begins with 0 again and continues the same cycle. Here is an example using mod 3.

0 mod 3 = 0 remainder 0
1 mod 3 = 0 remainder 1
2 mod 3 = 0 remainder 2 (i.e., m-1)
3 mod 3 = 1 remainder 0
4 mod 3 = 1 remainder 1
5 mod 3 = 1 remainder 2
6 mod 3 = 2 remainder 0 (m-1 again)

Conclusion
If we have integers A and B and we increase A by a multiple of B, we end up in the same spot. Thus,

3 mod 10= 3
13 mod 10 = 3
23 mod 10 = 3
33 mod 10 = 3

Problem: Find
(a) 311 mod 3
(b) 3 mod 4

Answers:
a): Since 311 is a multiple 77 of the modulo (4) with a remainder of 3, the answer is 3.
b) 3 mod 4 is 0 with a remainder of 3.

Notice that both 311 mod 4 and 3 mod 4 gives the same result. We say that they are in the same equivalence class.

311 mod 4 = 3, so is in the equivalence class 1, and
3 mod 4 = 3, so it is also in the equivalence class 1

Using ≡ to denote congruence modulo, we say 311 ≡ 3 mod 4. Note, however, that congruence does not imply that 311 = 3 mod 4.