High School Trig Is Powerful
Trying to cheat a decision problem
Leopold Kronecker proved many great theorems, including one on Diophantine Approximation theory. This is the theory of how closely real numbers can be approximated by rational numbers
. It has many beautiful results, with many applications, and is an early type of complexity theory.
Today I want to talk about a decision question that arose in reading a paper on number theory.
It’s a simple-to-state problem concerning equations involving cosine functions, yet seems hard to resolve. A partial solution involves—surprise—Kronecker’s famous theorem. I will explain his theorem in a moment, but first I must talk about trig functions.
Let state my feelings about such functions: I love and hate trigonometry. Let me explain why I love it, then we can move on to why I hate it. Okay?
Trig functions arise all over mathematics, have many interesting properties, and are critical to Fourier methods. In particular they play a major role in the analysis of some important number theory problems. The Prime Number Theorem, the statement that the number of primes less than is approximately
, is a deep theorem. We now have many proofs of this key fact about the behavior of the primes. Some use complex analysis, some are elementary, some use a combination of both.
A Motivating Example
Let me give an example of an innocent-looking identity:
,
which “factors out” the multiple of . Substituting this proves the identity (*):
It may seem amazing that deep theorems can be based on trig results like this, yet it is true. The reason it is so useful is that the identity implies the inequality,
One of the shortest proofs that the Riemann zeta function has no roots at for all real
was due to Franz Mertens, and uses the identity (*). He used the identity to prove that
satisfies:
The connection is that the real part of can be expressed using cosine functions—see here for more details.
Schooling Me on Equations
I can imagine that I was once asked to prove such trig identities back in high school—this is pretty basic. Speaking of high school that is why I hate trig. When I took it in school, it seemed like it was a lot of memorization—what is the definition of all those strangely named functions? Why not just use sine and cosine everywhere?
I also learned trig in summer school from a Mr. Ditka—I do not know his first name. He was like his name—tough—and later when I saw the professional football coach Mike Ditka on television I wondered if they might have been related. Both Ditkas were tough. Mr. Ditka, I can call him nothing else, taught me an important lesson about math. During that summer class I remember getting a problem wrong on an exam. I walked up to him after class with my exam and asked why I got zero points. The question was about writing down the equation for something, and the answer I had written was
I asked him why I got zero points, since this was the correct expression. Mr. Ditka looked at me and said,
I asked for an equation. You did not write an equation. Zero points.
He was right, if I had only added the equality sign and written
,
I would have scored full points. Oh well. Lesson learned.
Not The Question
I once tried to see if there were more general equations like the identity (*). I first thought about this question: Suppose
where the ‘s and
‘s. Is there an inequality like this?
The answer is that there is no such inequality. The reason is that any correct inequality must have a constant term. So without a constant term there is no such inequality. Here is the proof:
Suppose for all ,
where the and
are positive reals.
The key is to look at the integral —are we allowed to use integrals in theory? This flips the cosine functions to sine functions, and yields
evaluated at , since
. But for
just below
—or rather for
just below
—the expression becomes negative. This is a contradiction.
The Question
The real question concerns determining the possible values of a sum of cosine functions. This is a natural problem, but also has important application in number theory. Define a function by
We want to determine whether or not this function can be equal, even approximately, to some given value. Since the are fixed, it is a question in one variable—how hard can that be? The initial idea might be to just use calculus to solve the problem. But there is an issue. The function is defined for all real
, and therefore the answer can be any real number. Since this is an infinite interval, it seems to me that no standard search method works. If we could bound the limits of where we have to look for
then we could solve the problem.
The issue is that the arguments to the cosines have different periods, and we do not know in advance where or how their values might augment or cancel each other. The key insight is that Diophantine approximation theory allows us to factor out for integers
where they are unchanged, so that the remaining variation is restricted to a finite domain that can be searched. We would also like to iron out dependencies of the terms on each other, so that we get an easier-to-analyze system, such as a linear system.
An Example
Let’s look at an example first. Let
Suppose we want to know whether is approximately equal to some value
. How do we do this? The trouble, as we stated already, is that
is not restricted to a bounded interval, so standard methods do not apply. If we could restrict
to say
, then at worst we could try
at all the following values:
for some large .
The key observation is this: the numbers ,
, and
are linearly independent over the rationals. This follows since they are distinct primes. But now we can use Kronecker’s theorem. It is perfect for this situation.
Theorem: Let
be real numbers that are linearly independent over the rationals. Let
be arbitrary real numbers,
and
an integer. Then there exist integers
and an integer
such that for all
,
The theorem seems a bit complex at first glance, but we can use it to solve our problem—here is how. We have and
,
, and
. Also let
be arbitrary real numbers. The theorem shows there are integers
and
so that
for . This implies that
and clearly it follows that
Since cosine has period it follows that
is approximately equal to
, but this means that we can make
as close to any value that we like. Even more we can make each of the other cosines simultaneously have any value we like.
Thus, is equal to, within some small error,
where
are only constrained to be in the interval
. This constraint follows since cosine’s range is that interval. The point is that we can reduce the search for
to the solution of a linear system, which is easy. Done.
A Tougher Example
Note, this method works for any number of terms provided the logarithms are all independent. What happens if they are not? Things get more difficult—the above method fails, but not all is lost.
Let’s modify the previous example. Let
We can try to proceed as before, but the problem we hit is that
are not linearly independent over the rationals: .
All is not lost. We note that the method from the last section can be used on the three logarithms that are independent, and then state is terms of
. We get
where as before must lie in
. The value of
is
, since
We now can solve our problem since we have a polynomial question over a bounded domain. Done—again.
Extending the Idea, and a Problem
I had hoped that we might be able any cosine sums by the same trick. But alas I am stuck. We can handle cosine sums where all logarithms are primes or powers of primes. This follows since is a polynomial in
. Such polynomials are treated here.
The natural next step is to allow a term of the form . Unfortunately this appears not to be a polynomial in
and
. We can use the identity
but the substitution involves an absolute value as well as a radical.
Open Problems
Can this method be generalized to handle arbitrary cosine sums of this type?
A more general question is, perhaps there is a completely different approach to the whole question that solves it more directly. Any suggestions?
[clarified proof in “Not the Question” section, fixed some words]
I don’t think your proof in “Not The Question” is correct. For example, 1 is always greater than zero, but its integral does go below zero, in particular just to the left of the origin. The problem is that the integral means something different when the “lower bound” is greater than the “upper bound” of integration.
So… is there a nice short proof of the same fact? The most intuitive approach I can see is to consider x taken at random from a large interval. It’s intuitively clear and not hard to formalize that when x is u.a.r from the interval [0, M], the expectation E[sum_k a_k cos(x b_k)] tends to 0. This contradicts that the sum is bounded below by a positive constant. But it doesn’t rule out that the sum is always positive, yet gets arbitrarily close to zero. Could that be possible? Is there an easy proof of why not?
Wow, wow – slower, slower. Several typos, errors, and missing words. Which makes it somewhat difficult to follow. Please proofread carefully once more.
In the “Not the Question” section, when you integrate, the b_i’s go to the denominator, not the numerator.
Thanks to you and daveagp. I clarified the proof hopefully enough, and fixed up the prose in spots.
Still, the proof holds only for integral b_i (or b_i with the same denominator). For the full proof we probably need Kronecker’s theorem.
While you’re at it, don’t forget that evaluating integrals of the form
$\int_0^{2\pi} dx \prod_{i=1}^n \cos (a_i x)$,
for integers $a_1, \ldots, a_n$, is #P-complete!
Your notation as well as the proof in the section “Not the question” is still bad and misses the point: using a value “just below 2*Pi” of course doesn’t suffice, as for any such given value there is a linear combination of cosines which invalidates the claim (when trying to use this particular value as a witness). Also, the frequencies are not taken into account.
You have to use an approximation property as in the remainder of the article.
Also, integrating is unneccessary (might as well look at values of the cosine near its zeros).
Why is integral of 0 on right hand side of the cosine equation have to be 0? The right hand side of the sine equation will be some arbitrary constant not necessarily zero. Isn’t it?
silly me. definite int
In this regard, please let me commend to Gödel’s Lost Letter readers a computation-centric (and very readable) article by Martin Mohlenkamp and Lucas Monzón titled “Trigonometric identities and sums of separable functions” (Mathematical Intelligencer 2005).
In effect, Mohlenkamp and Monzón extend Dick Lipton’s question by asking: “What functions in high-dimensional spaces (like Hilbert spaces) can be given, or accurately approximated, by low-rank separable functions (like low-rank trigonometric functions)?”
As with Dick Lipton’s post, Mohlenkamp and Monzón discuss this question very entertainingly … without arriving a definitive answers to (what appears to be) an immensely large class of profoundly deep questions … questions whose answers in individual cases commonly have considerable practical importance.
So this was another wonderfully interesting, profoundly deep, eminently useful Gödel’s Lost Letter essay/question! 🙂
professor Lipton can you say more about why you hate high school trig? I also do not like trig identities because it seems like a bunch of formulas which have to be memorised and I end up forgetting them. Can you tell me if there are other elementary ways to look at trig, which links it to other parts of math and gives a deeper meaning to them? I am a student.