Newton’s inequality and log concave sequences

The previous post mentioned Newton’s inequality. This post will explore this inequality.

Let x be a list of real numbers and define Sn(x) to be the average over all products of n elements from x. Newton’s inequality says that

Sn−1 Sn+1S²n

In more terminology more recent than Newton, we say that the sequence Sn is log-concave.

The name comes from the fact that if the elements of x are positive, and hence the S‘s are positive, we can take the logarithm of both sides of the inequality and have

(log Sn−1 + log Sn+1)/2 ≤ log Sn

which is the discrete analog of saying log Sk is concave as a function of k.

Let’s illustrate this with some Python code.

from itertools import combinations as C
from numpy import random
from math import comb
import matplotlib.pyplot as plt

def S(x, n):
    p = lambda c: prod([t for t in c])
    return sum(p(c) for c in C(x, n))/comb(N, n)

N = 10
xs = random.random(N)
ns = range(1, N+1)
ys = [log(S(xs, n)) for n in ns]

plt.plot(ns, ys, 'o')
plt.ylabel(r"$\log S_n$")

This produces the following plot.

This plot looks nearly linear. It’s plausible that it’s concave.

Leave a Reply

Your email address will not be published. Required fields are marked *