#generating functions

100 days of productivity (229/primes)

I spent some time on reworking old algebra notes, and have now gone through most of the section about symmetric polynomials. I would like to finish this section tomorrow, but I will need to learn about Schur polynomials, so I’m not sure how this will go.

Track of the day: Burn the Witch by Radiohead

Question: Given any set \(A= \{a_1,...,a_n \} \) of integers such that no two subsets have equal sum, what is the maximum possible value of \( \sum_{i=1}^n \frac{1}{a_i} \)?

Answer: 2. Actually, it’s strictly less than 2.

Proof.

The brilliant part is the first step, encapsulating our assumption on \( A\) in a generating function. Let \(0 < x < 1\) and note that:

\[ \prod_{i=1}^n (1 + x^{a_i}) < \sum_{n=0}^\infty x^n = \frac{1}{1-x}. \]

Thus taking logarithms and dividing by \( x\) (because both are monotonic and respects the inequality) we see:

\[ -\sum_{i=1}^n \sum_{n=1}^\infty \frac{(-1)^n x^{a_i n-1}}{n} = \sum_{i=1}^n \frac{\log(1+x^{a_i})}{x} < - \frac{\log(1-x)}{x} =  \sum_{i=1}^\infty \frac{x^{n-1}}{n} .\]

Now, this looks ugly, but we integrate both sides, because the integral of the right hand side is actually something nice. Well, provided you put the integral inside the sum first, but this is legal thanks to the MCT. We find:

\[- \sum_{i=1}^n \sum_{n=1}^\infty \int_0^1 \frac{(-1)^n x^{a_i n}}{nx} dx  <  \sum_{i=1}^\infty \int_0^1 \frac{x^{n-1}}{n} dx ,\]

and so (changing \( x^{a_i} = y\) and \(a_i x^{a_i-1} dx = dy\)): 

\[- \sum_{i=1}^n \sum_{n=0}^\infty \int_0^1 \frac{(-1)^n y^{ n} }{n y a_i} dy <   \sum_{i=1}^\infty \frac{1}{n^2} =  \frac{ \pi^2}{6},\]

\[- \sum_{i=1}^n \frac{1}{a_i} \left(\sum_{n=0}^\infty  \frac{1 }{(2n)^2} - \sum_{n=0}^\infty  \frac{1 }{(2n+1)^2} \right) <  \frac{\pi^2}{6} ,\]

\[- \sum_{i=1}^n \frac{1}{a_i} \left(\frac{\pi^2}{24} - \frac{\pi^2}{8} \right) < \frac{\pi^2}{6} ,\]