In this blog post we present some basic quantitative results that show the polynomials of a fixed degree are good and predictable functions. It is also illustrated with two Olympiad problems. Let be a fixed natural number. We consider the set of all polynomials with real coefficients and degree at most Suppose, we know some information about a polynomial Then we can predict some other properties of For example, if the magnitude of is small in then it cannot become too large in a slightly expanded interval, say in . Its slope cannot become abruptly too steep. That is, by knowing some local properties of we can predict its behavior in nearby neighborhood. The main reason why it happens is that any polynomial in has finite number degrees of freedom. It is fully determined by finite and fixed number of parameters, for example by its coefficients. Below are some quantitative properties in this spirit.
Claim 1. (Markov’s inequality). Let be a polynomial of degree Then
That is, knowing that is not large in implies also cannot be too large in the same interval.
The following inequality is a generalization for the derivatives of higher order and is also attributed to Markov brothers.
Claim 2. (Markov brothers’ inequality). For any polynomial of degree it holds
Claim 3. Let be a polynomial of degree and we know the behavior of in the interval Then, we can predict the growth rate of of outside this interval. It holds
where is the Chebyshev polynomial of first kind. This is a famous extremal property of the Chebyshev polynomials. One can see a short proof of this fact in this blog post, as well as some of its applications.
Claim 4. For any polynomial we have
where is a constant depending only on
Proof. There are many possible approaches. We can use Markov brothers’ inequality. We also can use the Langrange interpolation formula for at some fixed knots, for example equally spaced in and then estimate the coefficients. I prefer a rather abstract approach, but it shows the ultimate reason why it holds. Consider the vector space of all polynomials of degree at most It can be normed by any of the following two norms
where . Since is a finite, dimensional vector space, any two norms are equivalent. It means there exist constants depending eventually only on so that
which proves Of course, the interval is not important, it can be replaced by any other interval, for example
Claim 5. For any polynomial we have
where is a constant depending only on
Proof. The same approach, by considering the norm
Problem 1 (Putnam 1995, A5). Prove that there is a constant such that, if is a polynomial of degree , then Solution. Straightforward, by Claim 5.
Problem 2. (Romanian NMO). Let be a times differentiable function so that:
Prove that: for , where is the -th derivative of .
Solution. It’s natural to use Taylor’s expansion.
We choose a large enough and vary in the interval So, the RHS of can be made as small as we want as and we want to show all are also small. Let us choose some Taking into account and the given conditions, there exists large enough such that for all and it holds
Using Claim 4, we get
where is a constant that may depend only on . Therefore
Let We say is progression-free if no three numbers in form an arithmetic progression. A natural question arises: What is the maximum size of in terms of Let us denote it by . This blog post is an overview (with two proofs) of some classical estimates of the growth rate of We consider the constructions of Salem-Spencer and Behrend that produce lower bounds on As we will see, the growth rate of is less than linear but it’s almost linear. It is still an open problem the exact asymptotic behavior of this value. Additionally, two Olympiad problems closely related to this question are provided. The first one is problem 5 of IMO 1983 and the second one was given at a Bulgarian TST for IMO 2012.
P. Erdős and P. Turan in  established some properties of and made a conjecture (they rather attributed it to G. Szekeres) that More specifically, G. Szekeres had conjectured This is true for but as we will see below it fails for large A short proof of was presented in the same paper of Erdos and Turan. The idea is to consider all numbers with digits base consisting only of digits (but not ). Interestingly, the same idea was used some 50 years later in IMO 1983, problem 5. Another common conjecture of those years was that there exists a constant such that In 1942 Salem and Spencer  disproved this claim by constructing an example of much larger sets that are progression-free. In 1946 Behrend  improved their construction and achieved a sharper lower bound of In the following years K. Roth proved the growth rate of was less than linear. More precisely, he proved for some absolute constant
An easy lower bound.
for some constant This construction is presented in . Let Consider all numbers with digits base consisting only of digits (but not ). It is easy to see no three of them form an arithmetic progression. Their number is and the maximum one is Thus, we get Here is a IMO problem that is based on the same idea.
Problem 1 (IMO 1983, problem 5). Is it possible to choose distinct positive integers, all less than or equal to , no three of which are consecutive terms of an arithmetic progression?
Solution. We use the above construction for Hence, we obtain a progression-free set of numbers less or equal to
As mentioned, there was a conjecture for some period of time that for some Until the result of Salem and Spencer appeared, which showed the growth rate of was much faster than that of and is “almost” linear. The idea is a refinement of the previous approach and also is based on considering natural numbers with digits base which comply with certain condition. Let and be natural number which values will be determined later and is multiple of Consider the family of all ordered sequences (we call them strings) of digits base i.e. the digits of each string in are We also want each string in to have the same number of occurrences of that is each digit to occur exactly times. It yields
Further, we consider the strings in as numbers base We denote the set of those numbers again as The key observation is that if some three numbers form an arithmetic progression (in this order) then their digits at any position also form an arithmetic progression. But this is impossible due to specific condition imposed on . Indeed, consider the zero digits of . At each of those positions there must be a zero digit in and . So, the zero digits occupy the same places in the three numbers. In the same way, we obtain the same fact for the positions of ‘s, ‘s, … , ‘s. Therefore, Hence, there is no arithmetic progression in Taking appropriate and large enough, Salem and Spencer obtained
for some constant which has a growth rate faster than for any
A couple of years later Behrend achieved a sharper lower bound estimate of His construction is based on the same idea, but the constraints imposed on are slightly different and the calculations are even simpler. We provide here the complete argument. Let and be natural number which values will be determined later. Consider the family of all ordered sequences of digits base Obviously, For any let denotes the sum of the squared digits of . Since there exists a subset and with
Now, consider the strings in as numbers base We claim they are free of arithmetic progressions. Indeed, suppose there exists three such numbers that form an arithmetic progression (in this order). Then their digits at any position also form an arithmetic progression, that is Therefore
Note, that this inequality is strict unless Summing up for and using are distinct numbers, we get
This contradicts the fact Hence, the strings in in base do not contain three term arithmetic progression. The corresponding numbers are less than and their number is at least Putting we established there exists a set of at least natural numbers less than Thus, putting we get
for some absolute constant
Problem 2. (Bulgarian TST for IMO 2012, p6.) Prove that for some natural number there exist natural numbers less than , so that there are no three of them that form an arithmetic progression. Solution. We use the above construction to obtain a set of numbers, each one less than Now, for large enough we take
The official solution I have seen, gives credit to Behrend and uses the exact construction given in this paragraph.
The previous two examples provide lower bounds of In 1953 Klaus Roth proved
for some absolute constant It means the growth rate of is less than linear. For example, given any (it may be very small), any subset of at least numbers in always contains an arithmetic progression when is large enough. There are some improvements of the given bounds but still, there is a gap between the lower and upper bounds of
References.  Erdős, Paul; Turán, Paul (1936), “On some sequences of integers” (PDF), Journal of the London Mathematical Society, 11 (4): 261–264. PDF  Salem, R.; Spencer, D. C. (December 1942), “On Sets of Integers Which Contain No Three Terms in Arithmetical Progression”, Proceedings of the National Academy of Sciences, 28 (12): 561–563. PDF  Behrend, F. A. (December 1946), “On sets of integers which contain no three terms in arithmetical progression”, Proceedings of the National Academy of Sciences, 32 (12): 331–332. PDF
This problem appeared at some Brazilian national Olympiad and is about a game on a graph. Very nice problem, but I think, problems like this should not be given at high school Olympiads. Because they depend on specific graph theory theorems which are not very popular. (Actually, there is another approach, see the thread in . So, I take my words back! I was also informed, see the comment below the blog post, it was given at the undergraduate level of the Brazilian NMO,15-16 March 2021, ) Two players. Each player marks a vertex on his turn, so that the marked vertex must be connected with the vertex marked on the previous move by the other player. No vertex is allowed to be marked twice, the player who cannot move loses. Ok, if the given graph has a perfect matching, the second player always wins. His strategy is very simple, he just marks the vertex that matches the one marked by the previous player. Surprisingly (for me), this condition is also necessary in order the second player to have a winning strategy. That is, if there is no perfect matching, the first player always wins. It may seem easy, but it is not. Here is the full text.
Problem 1 (Brazil National Math Olympiad, 2020). In a spacecraft, there are people, . Any two of them are either friends or enemies(the relationship is mutual). Two aliens play the following game: Alternately, each player chooses one person, such that the chosen one (of each round) is a friend of the person chosen by the other player in the previous round. In the first round, the player can choose any person, each person can be chosen in at most once, and the player, who cannot play anymore, loses the game. Prove that the second player has a winning strategy, if and only if, the people can be split into pairs, such that the people in each pair are friends.
Perfect matching. Some theory.
In order to solve the problem, we need some theory about perfect matching in general graphs. The main point of this section is to give a constructive characterization of any graph that does not have a perfect matching. I think Hall’s marriage condition is very popular and commonly used in Olympiad problems, but it is applied only for bipartite graphs. There is another result called Tutte’s theorem, which gives a similar condition for a general graph. But, we will need a stronger and a more constructive result. I follow the notations and results given in the wonderful book of R. Diestel, Graph Theory , chapter 2.2. – Matching in general graphs. Fortunately, this chapter is included as a sample chapter by the author, so one can freely download it – see . Let us begin with some notations first.
Notations. For any graph and a subset of its vertices, by we denote the graph that is obtained by by removing all the vertices in 1) For any graph by we denote the set of its (connected) components and by the number of its odd components, that is, those of odd order. 2) A graph is called factor-critical if and for each by removing the vertex we get a graph with a perfect matching. 3) We call a vertex set matchable to if the bipartite graph that arises when contracting each component into a single vertex and deleting the edges inside contains a matching of
Theorem 1. (Theorem 2.2.3. in ) For every graph there is a vertex set with the following two properties: 1) is matchable to . 2) All components in are factor-critical. Given any such set the graph has a perfect matching if and only if
The proof of this theorem is omitted here. One can find it in the mentioned book of R. Diestel . It goes by induction on the number of vertices in . Only this theorem will be needed in order to solve Problem 1, but I present below another interesting result which generalizes Hall’s marriage theorem.
Theorem 2. (Tutte, 1947, Theorem 2.2.1. ) A graph has a perfect matching if and only if for any vertex set
Proof of Problem 1. Let be the corresponding graph. We have to prove two things. 1) If has a perfect matching then the second player has a winning strategy. 2) If does not have perfect matching then the first player has a winning strategy. The first claim is obvious, we discussed it at the beginning. The second player always chooses the vertex that matches the one chosen by the other one. The second claim is what makes this problem difficult. We will use theorem 1. Let be a vertex set that is guaranteed by Theorem 1. Let and be the corresponding components in that are matched to i.e. there exist vertices such that Since does not have a perfect matching, by Theorem 1 there exists which is different from The strategy of the first player (call him and let the other one be ) is as follows. At his first move chooses some vertex Note that has a perfect matching. If chooses a vertex inside the player responds by choosing its counterpart that matches in Suppose, at some moment, leaves and chooses Then responds by marking Again, since has a perfect matching, upon any vertex that chooses inside the player responds by marking its counterpart that matches in If it happens leaves and jumps at vertex then sends into by choosing This continues like that and at some point will not be able to leave some either because all vertices in have already been marked, or because there is no edge back to and no other move inside is possible. Thus, the player wins.
Note that, the condition there are even number of people inside the aircraft (even number of vertices) is a redundant one. That is, it can be omitted. Of course if has a perfect matching the number of vertices is even. But in case does not have any perfect matching, the parity of the vertices is irrelevant.
A friend showed this problem to me, still unsolved in AoPS. Before reading on, you may just glance at its statement given below. We define an arithmetic function which value depends on the sum of the divisors of a given number and also on the Euler totient function . We are asked if there ere infinitely many for which is a perfect square. So, what to do? If there is one with such a property, there will probably be an infinite number of them. One possible option is to try to prove that there is no such . For example, by doing some modular arithmetic, or quadratic residues, or something. Especially, after trying enough values that do not bring perfect squares. By the way, the first for which is a perfect square is ! I didn’t go that far in the calculations, I only found it when I almost knew how to solve it. On the other hand, If one is convinced there are infinitely many such ‘s, which is a more reasonable conjecture, one could try to construct explicitly some kind of examples, which may lead to a pure NT chain of construction. Both approaches were not very fascinating to me, so at first, I was reluctant to think about the problem. Fortunately, the guy was persistent, he had thought and tried several things, and he was quite convinced that the approaches described did not work, and there must be another, to put it loosely: if you bring too many particles in a small room, some of them would bump into one another! In other words, he was convinced this problem had a combinatorial taste. And it indeed had, very tasteful one! So, back on the title. Yes, I think this problem is a number theory problem, and I welcome the trend of selecting problems which are on the border of various subjects. I hope you would enjoy this piece!
Problem (Rioplatense Math Olympiad, 2011, p6). For any , let denotes the sum of its positive integers divisors and – the number of positive integers up to that are relatively prime to . Example: and . Determine whether the set of all positive integers , such that is a perfect square, is finite or infinite.
Solution. Let It easily follows that for any with . We enumerate the prime numbers as
Claim. For any there is large enough for which there exists a subset that satisfies
is a perfect square.
Proof. You may think of as being fixed and – large enough which value will be determined later. Note that . Since both are even when we conclude that each prime factor of is less than or equal to Let be the greatest prime less than or equal to Thus, for any we have
where are non negative integers. Let us introduce the following dimensional binary vectors
for any We will prove for large enough. But let us first see why it helps. So, a pinch of linear algebra comes into use now. We have binary dimensional vectors and It means they are linearly dependent (as vectors modulo 2, i.e. as vectors in ) Hence, for some non empty subset it holds
which means is a perfect square. It remains to prove for sufficiently large Clearly where denotes the number of primes less or equal to On the other hand is the number of primes less or equal to By prime number theorem we have Hence, and which shows for sufficiently large .
Applying consecutively this claim, we can find as many as we want for which is a perfect square.
The following problem is a high quality inequality. Not a standard one. I don’t like the standard ones. I mean, all those one has to juggle when applying AM-GM (weighted version), power mean, Cauchy-Schwarz, Holder, etc. It is nothing more than pattern recognition and juggling with a bunch of cheap tricks. I don’t think such inequalities should be given at IMO or any high level math competition. It is my humble opinion, but I think so. It doesn’t mean one can miss these classic inequalities. Everyone who loves mathematics should learn them. They are useful, just like the multiplication table. Here is the statement of the problem, followed by a solution. In the last section, I outlined something about motivation.
Problem (JBMO 2014 shortlist). Let be a positive integer and be real positive numbers, such that . Prove that
Solution. In fact, we will prove something sharper: each of the terms and can be replaced with a convex combination of those of them which are less than (see below). Some notations first. Let
Note that cannot be empty and can be empty only when in which case the inequality is trivial. Thus, we can assume both are not empty sets. Denote and Let Clearly
Assume We have
In the same way, for any
Thus, it yields
Thus, in order to prove the original inequality, it is enough to prove
We will prove something even stronger. It holds
Let us first see why is sharper than By definition, Thus, the RHS of consists of two convex combinations of the points respectively and apparently
In order to prove we use
Hence, . Putting it back into we need to prove
for any satisfying Let The inequality is equivalent to
But, since and we indeed get which proves and hence holds.
Let first drop the two correction terms and and try to prove . Knowing we look to represent as . This brings two cases 1) and 2) . That’s why the sets come into consideration. So, all stuff up to the inequality comes up naturally. Jumping from to took me some time. I tried a few things before that. Actually, I even didn’t introduce the notations I worked with the minimal ones, and So, I came up with
It looks promising, because in case it obviously holds since
But, the way it’s written, it could fail in case is many times larger than and is small. This is quite possible. This happened because we dropped the bar (the LHS of ) too much beforehand. So, instead of a finer estimate needs to be made. That’s how appeared. This time, nothing like this can happen, because if is small then the average should be large because of
So, we are on the right track. Now, look again at the inequality . On its left hand side we see two linear combinations of , respectively while its right hand side is a sum of their minimum values. Therefore, we could try to improve by replacing , respectively with some convex combination of ‘s, respectively ‘s which is similar to that in the LHS. Once we get to , the following calculations are natural.
I was sent a problem from some Italian training camp, allegedly taken place in 2017. At least, the male name used in the problem statement was Italian, I think. Probably it was not from their official team selection test, but still I put it this way in the title. For sure, it is an interesting game problem with graph theory taste. I include it here as a perfect example how pairing works in certain types of games.
Problem(Italian training, 2017). Let be an integer and be circumferences in the plane such that, for each , the circles and have exactly two points of intersection and there is no point common to three distinct circles. There is a coin on each of the intersection points. Alberto and Barbara play a game: Starting from Alberto, each one takes a coin that is not on a circumference from which a coin has been removed in the immediately preceding round. During the first round, Alberto takes any coin he wants. The one that cannot make a valid move loses. Determine for which Alberto has a winning strategy.
Thus, every coin belongs to exactly two circles and every two circles have two coins on their intersection points. It is pretty clear, it’s not a geometry problem. Instead of circles it could have been ovals or some other curves. In order to filter irrelevant objects like circles, let translate the problem into graph theory language.
We have a complete graph with vertices (the vertices replace the circles). There are two coins on each edge of the graph. Alberto and Barbara play the described game of taking coins, and on each move the player cannot take a coin that is on any edge incident with the edge the previous coin was taken from.
I think, this is a better way to visualize what happens. Since we have a even number of coins, perhaps the second player could always make a move. There is a routine strategy in some of these games and it’s absolutely mandatory one to try it first. The idea is to pair the coins, so that the coins of each pair do not lie on incident edges. If this is possible then the second player, Barbara, wins – she just takes the coin that is paired with that previously taken by Alberto. We prove such pairing is possible when . In case obviously Alberto wins, since after removing any coin, the other player cannot touch anything. Thus, the answer is, Alberto has a winning strategy only when .
Assume Let, as usual, be the set of the edges of We will construct a bijection with the following properties. For each the edges and are not incident and the same holds for the edges and Enumerate the vertices of as By convention, for any and integer we assume where and For any edge for which and are not consecutive (we assume and are consecutive), we define . When and are consecutive vertices, i.e. we define Note that , since Now, the mentioned property of clearly holds. The action of on the elements of partitions into cycles For each such cycle let and be the two coins on We pair the coin with for By the mere construction of , any pair of coins lie on edges that are not incident. As described, Barbara just takes the coin that is paired with the one taken by Alberto and wins.
No, no, I wouldn’t oppose these two great minds. I’ll comment on two of their famous results – Godel’s incompleteness theorem and Turing’s proof that the halting problem is undecidable. They are similar in the sense they are based on the similar ideas. The main point of this blog post is to show Godel’s incompleteness theorem is a short corollary from the Turing’s result on the undecidability of the halting problem. We will prove the both theorems. I promise, there is no need of any deeper understanding of logic other than a notion what a program is and a vague clue what a deduction is.
By “Turing machine” one can imagine a computer with a program that runs on it. This computer has infinite amount of storage (for example, RAM) and can print on infinite roll of paper. It takes as an input, a binary string with finite length, and processes it. While processing the input, the program may produce some output and may eventually halt or this process may run forever. For example, one may write a program in C++ that reads the first symbol of the input and outputs it (prints it) forever, or a program that reads the first symbol, prints it exactly 100 times, and then halts. Both programs would be simple ones, so upon seeing them one can judge whether the process stops or runs forever. But imagine a more complicated program. It may take a long time to study it and decide whether it halts or runs forever! Here is a natural question that arises. Does there exist an algorithm, that given any program and input, decides whether this given program halts on this input? By algorithm I mean a written program. So, could we write a software (maybe a very complicated one) that takes as input: 1) a program (its source code) and 2) some input (binary string) , and then decides whether halts on the input ? What Turing proved was that such software could not exist! That is, the halting problem is undecidable.
Turing’s result: the halting problem is undecidable.
Suppose, for the sake of contradiction, there exists a Turing machine which takes as input pairs , where is a Turing machine and is a string. You may imagine the program (Turing machine) is represented by its source code, which is a finite string over an alphabet of finitely many symbols. There is some delimiter (a special symbol, or some other convention) that separates the two strings and , so that knows which part of the input is and which one is . Further, runs some inspection on and and prints out whether halts on the input or it runs forever. We assume that for some pairs the first string may not be a valid Turing machine (valid program). We know how to discern between a valid program and some gibberish. In the latter case outputs that is not a valid program. Let us construct the following Turing machine Given any input string the machine simulates the result of on the input , that is, runs with the input . In case is not a valid program, prints it out. In case is a valid program, will find out whether halts on the input or runs forever. In the former case runs forever and in the latter one it halts. In other words, processes a given string by doing just the opposite of what does on the string Now, we will finish in just one sentence! Think about what would happen if takes as an input its own code As defined, on does just the opposite of what on does!! That’s it, we got a contradiction. Hence, there does not exists a Turing machine that decides the halting problem.
A very short proof. I was astounded upon seeing it for the first time, many years ago as a freshman in college. Not because there is something very involved; it resembles somehow the Cantor’s diagonal argument, and I was also aware of Godel’s results. But because of the limitations it imposes on the human knowledge. The Godel’s theorems are also in the same spirit, but they are more abstract. If there exist unprovable claims in some theory, you may add another axiom and expand the things you can prove. For example, the Euclid’s fifth postulate. Whereas, Turing bluntly proved we are limited. We cannot invent an algorithm that, upon inspection of a given program, decides whether it has a bug (and thus may enter a cycle and run forever) or it is flawless! Alan Turing proved it when he was 24! We omitted some technical details. For example, we take it for granted what a Turing machine is, because we know what a program is and what a computer is. There were no such things in those times, though. So, Turing invented a construction (later called Turing machine) and showed how it can be described as a mathematical object. He also constructed the so called universal Turing machine , that takes as an input any Turing machine (or rather its encoding as a string) and an input then simulates over the input In now days we encounter this behavior everyday. For example, this is what any operating system does. It loads a program and operates it over an input. It is also what any virtual machine does.
Gödel’s incompleteness theorem.
Suppose we have in our disposal a theory that consists of some finite number of axioms that include the arithmetic properties of the natural numbers. We have deduction rules that allow us make deductions and prove theorems. Suppose this theory is consistent, i.e. we cannot prove (using the rules) both a theorem and its negation. We assume also we can check if a proof of some theorem is a valid one. The last assumption is a natural one, since the proofs must be checkable. Under these assumptions, Godel proved, there exists a claim in this theory that is unprovable and its negation is also unprovable. He constructed a sentence (claim) with a circular reference to itself, something like the one used in the liar paradox: “This claim is unprovable”. So, it is neither provable nor disprovable. In order to do it, Godel map each sentence to a natural number, the so called Godel’s numbers. That’s why, the natural numbers should be included into the theory. The classical proof of Godel is rather long and tedious, because of the technical details. Here, we present a short proof using the Turing’s result.
Suppose on the contrary, any valid claim which is not gibberish, can be either proved or disproved. We will show the halting problem is decidable, which would be contradiction. Take any Turing machine and an input Consider the following two sentences, “ eventually halts over the input ” and “ doesn’t halt, when it takes as an input, and runs forever”. The two sentences can be translated into valid claims of our theory about natural numbers. Indeed, we can define what does as consecutive steps operating over some sets of objects like we have some input, which is an ordered set of symbols and we apply some instruction which depends on the internal state of the machine which leads to recursively defining a sequence of sets. We are asked whether this sequence of sets reaches some final set which we view as a halting state. So there is a proof that proves either or because one theorem is the negation of the other one. This proof consists of finite number of symbols, so we can enumerate lexicographically all finite strings as candidate proofs and then proceed to check them one after another. Thus, after some time, we’ll find a proof of either or thus finding out where halts or not. This description can be implemented as an algorithm, hence the halting problem is decidable, contradiction.
We have already presented (in a previous blog post) how the discrete Fourier transform is useful in some Olympiad problems. Two problems were considered – a Chinese TST problem and a an IMO shortlist problem. Both of them dealt with a partition of the set of all integers into (three or four) sets with a given pattern. So, it’s no doubt why the Fourier transform is applicable to problems like these – it itself is designed to reveal patterns. In this blog post I present to you a problem from APMO 2013 (Asian Pacific Mathematics Olympiad). Two sets are given, which comply with a pattern that brings them together. This time, we use the continuous Fourier transform (not the discrete one). I will first give the problem statement, followed by the definition of the Fourier transform together with a few basic properties. Finally, the solution is presented.
Problem (APMO 2013, Problem 4). Let and be positive integers, and let and be finite sets of integers satisfying
(i) and are disjoint; (ii) if an integer belongs to either to or to , then either belongs to or belongs to .
Prove that . (Here denotes the number of elements in the set )
If you know the basic properties of Fourier transform jump to the solution section. Let be integrable function. We define
Thus, the obtained function is called Fourier transform of function Loosely speaking, it may be viewed as being a frequency decomposition of
The following property shows how to find the Fourier transform of an offset of For any
Imagine a river with two banks. Some good functions live on one side, and on the other side (the Fourier side)- their Fourier transforms. Each function is related with its Fourier counterpart. So, shifting a function by an offset on one side corresponds to multiplying its Fourier transform by on the Fourier side. This picture is common for many other Fourier properties. For example, multiplying any two function on one bank corresponds to taking their convolution on the Fourier side. The Fourier transform also preserves inner product. The inner product of two functions on one bank is the same as the inner product of their transforms on the Fourier side. There is a way to recover a function knowing its Fourier transform. So called inverse Fourier transform.
Ok, this information is more than enough to solve this particular problem. Oh, as I see now, we need another fact. For some wide class of functions the corresponding Fourier transform is everywhere differentiable. It certainly holds when is a bounded function with a compact support.
Back to the problem.
The given condition just means that
where, as usual, We have because and are disjoint. Therefore, Since it follows and are disjoint and
Let us denote
Clearly, a similar condition as holds for
Let and be the indicator functions of sets correspondingly By we get
Taking the Fourier transforms of the left and right sides, and using it yields
Further, we differentiate with respect to the both sides of the above equality. As mentioned in the above section, and are smooth.
Putting it yields
By the mere definition of (see ) it follows where denotes the measure (total length) of In the same way, Finally,
Finally, I decided to comment on this remarkable problem. It stayed for a couple of months in my drafts here. I postponed it several times – at first there was an error I found when writing the proof. After that, some details had to be elaborated. By the way, the most reliable way to verify your own proof is to write it down. Anyway, let’s proceed with the problem itself.
Problem 6 (IMO 2020). Prove that there exists a positive constant such that the following statement is true: Consider an integer , and a set of points in the plane such that the distance between any two different points in is at least . It follows that there is a line separating such that the distance from any point of to is at least . (A line separates a set of points if some segment joining two points in crosses .) Note. Weaker results with replaced by may be awarded points depending on the value of the constant . Proposed by Ting-Feng Lin and Hung-Hsun Hans Yu, Taiwan.
We fix some , which exact value will be determined later. Let us draw a circle with radius around each point in and let the polygon be the convex hull of . We want to show there is a line that intersects and does not meet any circle. Denote by the perimeter of the polygon . We’ll consider two cases. The first case is when the interior of is “too densely” packed with circles of radius (thou, the distance between any two of their centers is at least ). In this case we do not allow the line to penetrate deeply into the interior of , because there are “too many” circles inside it and it would meet someone. We rotate the line and allow it to cut off only a “small piece” of the the polygon . The second case is when the perimeter of is “too large”, i.e. the small circles of radius are not tightly packed inside . It’s dealt in a routine manner. We project on an appropriate line (the line on which has the longest projection) and establish that some line that is perpendicular to does not meet any circle. I put more details about the motivation in the last section of this blog post.
Let the polygon be the convex hull of . Denote by the perimeter of . Fix some , which exact value will be determined later.
Suppose some exterior angle of the polygon is greater than Then we can chose a line at distance from that vertex that cuts off a very small corner from the polygon – see at figure 1.
Let and touches the circle with center and radius A straightforward calculation yields or which means cannot meet any other circle (for sufficiently large n), and we are done. Thus, hereafter are under the following assumption. Assumption 1: Every exterior angle of is at most Further, we consider two cases, and start with the harder one.
First case: . According to the assumption, every exterior angle of is less than For any (further by we mean the contour of the polygon) let be the point at distance measured clockwise, along the polygon, i.e. the broken line between and has length Let be the maximum distance such that translating the line at distance toward the direction outside the polygon, it still meets Thus, depends on We can parameterize as being at distance measured clockwise alongside the polygon, starting from some fixed point Each such corresponds to a point and Consider the region defined as
Each point corresponds to a line that intersects namely, we take that corresponds to and translate it at distance outward (dotted lines in the fig. 2 below).
Denote by the family of all those lines, i.e.
We claim there is a line that does not meet any circle. In order to prove this, we establish three auxiliary facts.
Claim 1. The area of is at least for some absolute constant
Claim 2. For any let be the circle with center and radius Let be the subset of that corresponds to the lines intersecting Then
where is an absolute constant, and means the area of
Claim 3. The lines in intersect at most circles for some absolute constant
Before proving the above claims, let us first see how they help us to prove the statement of the problem. Let be the set of those points for which some line in intersects We have
Using claims 2 and 3, we get
Now, we choose Because it yields
According to claim 1, it holds therefore there is a point in which does not belong to the set of “bad” points and the result follows.
Proof of Claim 1. We can partition the contour of into pieces, which number is bounded by an absolute constant, in such a way that each piece can be rotated appropriately so that the slope of its leftmost segment is and the slope of its rightmost segment is Let be the equation of some such rotated piece, where is a concave function in and For any by we denote the length of the projection of the segment on the axis. Due to assumption 1, the slopes at the points and differ no more than hence
for some absolute constant In order to estimate a lower bound for we replace with a smaller segment connecting the points and where Respectively is replaced by the maximal distance between and the segment when We denote this distance by Clearly We further approximate by the length of the vertical segment that lies on the vertical line through and that is between the graph of and the segment (see figure 3).
Its length is Since the slope of is not too big, we have for some absolute constant and it boils down to find a lower bound for
for an absolute constant
Proof of Claim 2. Let be the first point for which touches Take any point at distance slightly more than from taken alongside Since the slope of is changing slowly (due to assumption 1) the segment does not intersect (see figure 4).
Therefore, each for which intersects satisfy Note that the distance between and alongside the contour of is less than thus For each the translations of the segment that still intersect the circle lie in some interval with length thus the result follows.
Proof of Claim 3. It boils down to prove for some absolute constant The proof of it goes in the same lines as that of Claim1.
Second case: (the circles are not “tightly” packed inside ). Pick a line such that the projection of on is the longest possible one. Then for some absolute constant (in fact ). For each construct a circle with center and radius The projection of on the segment is a segment with length at most The sum of those projections is at most . Therefore, there is a point such that the line through and perpendicular to does not meet any circle
Something about motivation.
It’s a natural idea to consider the convex hull of the given set of points . So, we are looking for a line that intersects but does not intersect any of the circles with centers at the points in and radii where is not too much lesser than One can try the idea described in the second case of the above argument. It’s a routine idea. So, it works, but only in case the perimeter of is greater than (or for some (small) absolute constant ). The other case, is more interesting. I tried first a configuration where is close to a circle. I tried to consider lines that do not penetrate too deep into We take a line that is tangent to the circle and begin to rotate it keeping it tangent, and at each rotation we translate it at a distance at most toward the center of This is our family of lines. Each line in can be described with two parameters: the angle of the rotation and the distance the line is translated towards the center of So, the set is exactly the rectangle and has area exactly For a fixed small circle it can be easily calculated the area of that part of that corresponds to the “bad” lines intersecting (figure 4 may be helpful, just imagine were a circle). It’s something like where is the radius of We have So, the portion of the bad lines for each small circle is less than some constant multiplied by But there are less than points of in the annulus with width and outer radius Hence, if we sum up the areas corresponding to the bad lines for each of these points, and take for some small constant , we get the total bad area is less than therefore some line does not meet any small circle. I did these calculations assuming was a circle and it looked promising. But there are many obstacles if one follows exactly the same approach in general. It seems a translation with a fixed step at each angle of rotation cannot be generalized seamlessly.
A problem about the rate of convergence of a recursive sequence. Imagine we have a recursive sequence where Clearly is monotonic decreasing and converges to The point is: how fast? I include it here because of the curious idea. Not unusual one, but still interesting. Look at the factor Each time we multiply the previous term by this factor to get the next one. If it were a constant we would have dealt with a geometric progression. But this factor is changing, it is getting closer and closer to thus slowing down the way decreases. So, the idea is simple and common. If you have a process that at each step depends on some variable that is changing, then divide this process into stages, where this variable is relatively constant, and treat it at each stage as if the variable is constant. Another point that deserves attention: instead of looking for a lower bound for we take some (for example ) and estimate how many terms of the sequence are larger than It is an equivalent approach because is a decreasing sequence. Here is the original problem.
Problem (Brazilian Undergrad MO 2017 P4). Let be a sequence of strictly positive terms with such that, for some and for all ,
Prove that there exists such that
Solution. Consider the sequence
where and is chosen in such a way that Since the function is monotonic increasing in the interval and in this interval, it follows (by induction) Thus, it boils down to prove the claim for the sequence . Unfortunately, I do not know an explicit way to describe this sequence. But look at the recurrence relation and the term This term is approaching as So, we can view upon as a geometric progression, but with varying ratio which is getting closer to and thus, slows down the rate of decreasing of the geometric progression. The idea is to partition the sequence into stages such that at each stage the ratio isn’t changing too much, i.e. it remains approximately the same up to multiplying by some absolute constant. So, the plan is to partition into intervals and to estimate the number of terms of the sequence in each interval. Whenever the ratio It means for any we have
Let be the term of the sequence that enters for the first time the interval It always hits the second half of this interval for large enough So, because of the term never exits while it holds
The above inequality holds for any where is a constant depending only on Thus, for large enough at least terms of the sequence are inside Summing up the terms over it follows at least terms are greater than for large enough where is a constant (depending only on ). Since the sequence is monotonically decreasing, the result follows.
Note that in this way we have actually proved the existence of two constants such that