What does Chowla's cosine problem actually ask to find?

92 Views Asked by At

The problem according to this description is:

Let $ A \subseteq {\mathbb N} $ be a set of $ n $ positive integers and set $m(A) = - \min_x \sum_{a \in A} \cos(ax).$

What is $ m(n) = \min_A m(A) $?

What baffles me is how function $m$ first takes a set $A$ as an argument, then takes number $n$ as an argument, all in the same equation. What's more, while there's a need to minimize over $x$, the second equation asks to minimize also over $A$. Are we just allowed to pick any $A$ of $n$ elements and any real $x$ we want?

Could someone, please, clarify the ambiguous use of $m$ and provide an example to show some intuition behind the statement of the problem?

1

There are 1 best solutions below

1
On BEST ANSWER

I find it helpful to imagine these minimax type problems as a game. For each $n$, we can imagine the following procedure:

  1. You pick a set of $n$ integers
  2. I pick a value of $x$,

The score of the game is the value of $\sum (-\cos(ax))$. I'm trying to maximize the score, you're trying to minimize it.

No matter what set you pick, I can always score at least $0$ -- if I just choose a random $x$ between $0$ and $2\pi$, then on average $\cos(ax)$ will be $0$. So the average score if I played completely at random would be $0$. But this is just an average. I'm allowed to pick whatever $x$ I want, so I can look at your choice of $A$, observe how the sum varies with $x$, and choose accordingly. So in practice I can always score something positive.

Your strategy is to minimize the benefit I can get from choosing $x$ after you choose $A$-- you're looking for a choice of $A$ so that the sum doesn't vary too much with $x$, and the maximum isn't too large.

The Chowla problem is asking for the score of this game when you and I both play optimally