High School Trig Is Powerful

August 31, 2012

tags: decision procedure, Diophantine, Problems

by rjlipton

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 ${r}$ can be approximated by rational numbers ${a/b}$ . 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 ${x}$ is approximately ${x/\ln x}$ , 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:

$\displaystyle \cos(2x) = 2\cos^2(x) - 1$ ,

which “factors out” the multiple of ${2}$ . Substituting this proves the identity (*):

$\displaystyle 3 +4\cos(x) + \cos(2x) = 2(1+\cos(x))^{2}.$

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,

$\displaystyle 3 +4\cos(x) + \cos(2x) = 2(1+\cos(x))^{2} \ge 0.$

One of the shortest proofs that the Riemann zeta function has no roots at ${s= \sigma + it}$ for all real ${t}$ was due to Franz Mertens, and uses the identity (*). He used the identity to prove that ${\zeta(s)}$ satisfies:

$\displaystyle \zeta(\sigma)^{3}|\zeta(\sigma + it)^{4}\zeta(\sigma + 2it)| \ge 1.$

The connection is that the real part of ${1/n^{s}}$ 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

$\displaystyle x^{2} -x + 1.$

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

$\displaystyle x^{2} -x + 1 = 0$ ,

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

$\displaystyle a_{1}\cos(b_{1}x) + \cdots + a_{m}\cos(b_{m}x) \ge 0,$

where the ${a_{i}>0}$ ‘s and ${b_{i} > 0}$ ‘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 ${x}$ ,

$\displaystyle f(x) = a_{1}\cos(b_{1}x) + \cdots + a_{m}\cos(b_{m}x) \ge 0,$

where the ${a_{i}}$ and ${b_{i}}$ are positive reals.

The key is to look at the integral ${\int_{0}^{t} f(x)dx}$ —are we allowed to use integrals in theory? This flips the cosine functions to sine functions, and yields

$\displaystyle \frac{a_{1}}{b_{1}}\sin(b_{1}x) + \cdots + \frac{a_{m}}{b_{m}}\sin(b_{m}x).$

evaluated at ${x=t}$ , since ${\sin(0) = 0}$ . But for ${x}$ just below ${0}$ —or rather for ${t}$ just below ${2\pi}$ —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 ${f}$ by

$\displaystyle f(t) = \sum_{k=1}^{m} a_k \cos(t \ln k).$

We want to determine whether or not this function can be equal, even approximately, to some given value. Since the ${a_k}$ 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 ${t}$ , 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 ${t}$ 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 ${2\pi p}$ for integers ${p}$ 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

$\displaystyle f(t) = a \cos(t\ln 2) + b \cos(t \ln 3) + c \cos(t \ln 5).$

Suppose we want to know whether ${f(t)}$ is approximately equal to some value ${v}$ . How do we do this? The trouble, as we stated already, is that ${t}$ is not restricted to a bounded interval, so standard methods do not apply. If we could restrict ${t}$ to say ${[0,1]}$ , then at worst we could try ${t}$ at all the following values:

$\displaystyle 0, \frac{1}{N}, \frac{2}{N}, \dots, \frac{N-1}{N},1,$

for some large ${N}$ .

The key observation is this: the numbers ${\ln 2}$ , ${\ln 3}$ , and ${\ln 5}$ 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 ${1,\alpha_{1},\dots,\alpha_{\ell}}$ be real numbers that are linearly independent over the rationals. Let ${\nu_{1},\dots,\nu_{\ell}}$ be arbitrary real numbers, ${\epsilon>0}$ and ${N>0}$ an integer. Then there exist integers ${q_{1},\dots,q_{\ell}}$ and an integer ${t > N}$ such that for all ${i}$ ,

$\displaystyle | t\alpha_{i} - \nu_{i} - q_{i} | < \epsilon.$

The theorem seems a bit complex at first glance, but we can use it to solve our problem—here is how. We have ${\ell = 3}$ and ${\alpha_1 = \frac{\ln 2}{2\pi}}$ , ${\alpha_2 = \frac{\ln 3}{2\pi}}$ , and ${\alpha_3 = \frac{\ln 5}{2\pi}}$ . Also let ${\nu_{1},\nu_{2},\nu_{3}}$ be arbitrary real numbers. The theorem shows there are integers ${t}$ and ${q_{1},q_{2},q_{3}}$ so that

$\displaystyle | t\alpha_{i} - \nu_{i} - q_{i} | < \epsilon.$

for ${i=1,2,3}$ . This implies that

$\displaystyle \left| t \frac{\ln 2}{2\pi} -\nu_{1} - q_{1} \right| < \epsilon,$

and clearly it follows that

$\displaystyle \left| t \ln 2 -2\pi \nu_{1} - 2\pi q_{1} \right| < 2\pi\epsilon.$

Since cosine has period ${2\pi}$ it follows that ${\cos(t\ln2)}$ is approximately equal to ${\cos(2\pi\nu_{1})}$ , but this means that we can make ${\cos(t\ln2)}$ 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, ${f(x)}$ is equal to, within some small error, ${ax+by+cz}$ where ${x,y,z}$ are only constrained to be in the interval ${[-1,1]}$ . This constraint follows since cosine’s range is that interval. The point is that we can reduce the search for ${t}$ 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

$\displaystyle f(t) = a \cos(t\ln 2) + b \cos(t \ln 3) + c \cos(t \ln 4) + d \cos(t \ln 5).$

We can try to proceed as before, but the problem we hit is that

$\displaystyle \ln2, \ln 3, \ln 4, \ln 5$

are not linearly independent over the rationals: ${2\ln 2 - \ln 4 = 0}$ .

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 ${\cos(t \ln 4)}$ is terms of ${\cos(t\ln2)}$ . We get

$\displaystyle ax + by +cw +dz,$

where as before ${x,y,z}$ must lie in ${[-1,1]}$ . The value of ${w}$ is ${2x^{2}-1}$ , since

$\displaystyle \cos(2\theta) = 2\cos^{2}(\theta)-1.$

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 ${\cos(nx)}$ is a polynomial in ${\cos(x)}$ . Such polynomials are treated here.

The natural next step is to allow a term of the form ${\cos(t \ln 6)}$ . Unfortunately this appears not to be a polynomial in ${\cos(t\ln2)}$ and ${\cos(t\ln3)}$ . We can use the identity

$\displaystyle \cos(x + y) = \cos(x)\cos(y) - \sin(x)\sin(y),$

but the substitution ${|\sin(x)| = \sqrt{1 - \cos^2(x)}}$ 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]

	PrincetonPete on Muffins and Integers
	calebstanford on Muffins and Integers
	Caleb Stanford on Muffins and Integers
	The Muffin Problem… on Muffins and Integers
	KWRegan on Muffins and Integers
	Javaid Aslam on Lost in Complexity
	Timothy Chow on How to Check a Proof
	Eftychis on Does 1 Times 1 Equal 2?
	Roy Abrams on Does 1 Times 1 Equal 2?
	Frank Vega on Can Amateurs Solve P=NP?
	Jhon Hard on Hilbert’s Irreducibility…
	Jhon Hard on On the Edge of Eclipses and…
	How the Villarino-Ga… on Hilbert’s Irreducibility…
	Carnival of Mathemat… on Does 1 Times 1 Equal 2?
	test on Hilbert’s Irreducibility…

a personal view of the theory of computation

High School Trig Is Powerful

A Motivating Example

Schooling Me on Equations

Not The Question

The Question

An Example

A Tougher Example

Extending the Idea, and a Problem

Open Problems

Leave a Reply Cancel reply

Subscribe to Gödel’s Lost Letter

Our Book

Recent Posts

Top Posts

Recent Comments

Blogroll

Archives

Sitemeter

a personal view of the theory of computation

High School Trig Is Powerful

A Motivating Example

Schooling Me on Equations

Not The Question

The Question

An Example

A Tougher Example

Extending the Idea, and a Problem

Open Problems

Share this:

Like this:

Related

Leave a Reply Cancel reply

Subscribe to Gödel’s Lost Letter

Our Book

Recent Posts

Top Posts

Recent Comments

Blogroll

Archives

Sitemeter