Is this product always greater than these sums?

[JFGariepy]

I've been working on a problem for a couple of days now and I wanted to see if anyone here had an idea whether this was already proven or where I could find some guidance. I feel this problem is connected to the multinomial theorem but the multinomial theorem is not really what I need . Perhaps someone on this forum knows how this problem would be named and even how to solve it. I feel like this should be easy to prove and I've proven single specific cases but I can't wrap my head around the more general case and in fact have no idea whether it's provable, proven, or even true.

So we have a set ω containing n numbers referred to as P₁, P₂, P₃...

Each of these numbers is a distinct prime number greater than 4. It may or may not be relevant to the proof, but ω always contains all qualifying prime numbers up to a certain number, so it would be impossible to have missing prime numbers, and the following set would be impossible (ω = P_1:3 = [5, 7, 13]). You can only have ω that include all prime numbers up to a point, such as (ω = P_1:3 = [5, 7, 11]), or (ω = P_1:2 = [5, 7]).

Note that because all elements of ω are ordered and distinct, and that 5 is always present in the set, we can write them as prime gaps being added to 5 in the following way:

P₁ = P₁ = 5
P₂ = P₁ + PG₂ = 5 + 2 = 7
P₃ = P₁ + PG₂ + PG₃ = 5 + 2 + 4 = 11
...

where PG_i reads "the prime gap associated with P_i" and where the indexing of the gaps starts at P₁ = 5, and PG₁ = 0.

So to recapitulate the conditions in a cleaner list:

Conditions

ω contains all distinct prime numbers between 4 and a given integer (condition 1)

ω has a certain size n > 1 (condition 2)

Due to Bertrand's postulate, note that any PG_i < P_i.

Specific formulation of the problem (this is an equivalent of the general case with m = n)

Prove that for any given ω with number of elements n > 1, the product of all P in ω is greater than the sum of the products of all possible combinations of subsets of ω with size n - 1.

So, for instance, for n = 2, prove that:

P₁P₂ > P₁ + P₂

or, for another instance with n = 4, prove that:

P₁P₂P₃P₄ > P₁P₂P₃ + P₁P₂P₄ + P₁P₃P₄ + P₂P₃P₄

General formulation of the problem

Prove that for any given ω with number of elements n > 1, given any chosen integer 1 > m ≤ n, the sum of the products of all possible combinations of subsets of ω with size m is greater than the sum of the products of all possible combinations of subsets of ω with size m - 1. So, for instance:

for n = 4 and m = 3,

P₁P₂P₃ + P₁P₂P₄ + P₁P₃P₄ + P₂P₃P₄ > P₁P₂ + P₁P₃ + P₁P₄ + P₂P₃ + P₂P₄ + P₃P₄

or for n = 5 and m = 4,

P₁P₂P₃P₄ + P₁P₂P₃P₅ + P₁P₂P₄P₅ + P₁P₃P₄P₅ + P₂P₃P₄P₅ > P₁P₂P₃ + P₁P₂P₄ + P₁P₂P₅ + P₁P₃P₄ + P₁P₃P₅ + P₁P₄P₅ + P₂P₃P₄ + P₂P₃P₅ + P₂P₄P₅ + P₃P₄P₅

Example proof

I've had success handling single cases by expressing all primes as being an addition of prime gaps with 5, for instance:

Proof for m = 2 and n = 2

Prove that P₁P₂ > P₁ + P₂

We know that P₂ = P₁ + PG₂, therefore:

P₁(P₁ + PG₂) > P₁ + P₁ + PG₂

P₁² + P₁PG₂ > 2P₁ + PG₂

We may label these 4 terms as term 1, 2, 3 and 4. It is easy to see that term 1 is greater than term 3, because P₁ > 2 (condition 1). It is also easy to see that term 2 is greater than term 4, because P₁ > 1 (condition 1).

Therefore the left side has to be greater than the right side.

Help needed!

I'd love to see if anyone has some guidance to provide on proving the general case. It feels like this is strongly related to the Pascal triangle and multinomial theorem but I have difficulties finding where to start.

 

[JFGariepy]

The line "Due to Bertrand's postulate, note that any PGi < Pi" should have read:

Due to Bertrand's postulate, note that any PGi < P_i-1

 

[mfb]

The special case is wrong. Divide both sides by the product, and it is claiming 1 > 1/5 + 1/7 + 1/11 + ... up to some prime number P. The sum of inverse prime numbers diverges, so there are prime numbers where this inequality is violated.

General case:

given any chosen integer 1 > m ≤ n

There are not many integers smaller than 1. Do you mean 1<m?

I don't think prime gaps are useful here.

 

[JFGariepy]

You're totally right, I mean 1 < m . In the case where the statement is false, I'm interested in identifying for which m and n it would be true.

 

[JFGariepy]

The special case is wrong. Divide both sides by the product, and it is claiming 1 > 1/5 + 1/7 + 1/11 + ... up to some prime number P. The sum of inverse prime numbers diverges, so there are prime numbers where this inequality is violated.

General case:
There are not many integers smaller than 1. Do you mean 1<m?

I don't think prime gaps are useful here.

I have checked and indeed 109 is the prime at which the 1 > ... inequality is violated. Thank you very much for pointing that out, I guess I now have to go back to the workbench and see what reformulation I could find and what kind of boundaries I would put on m and n.

 

[mfb]

It is not valid for m=n as established, and it is valid for no m. Proof:

Let S(p₁,p₂) be the sum of inverse primes from p₁ to p₂ inclusive, e.g. S(5,11)=1/5+1/7+1/11.
Let p_n be the nth prime larger than 4, e.g. p₁=5.
Let A(n,m) be the sum of all possible products of m distinct primes out of the first n primes p_i, divided by the product of those n primes, e.g.
A(3,2)=(5*7+5*11+7*11)/(5*7*11)=1/5+1/7+1/11=S(5,11)
A(3,1)=(5+7+11)/(5*7*11)=1/(5*7)+1/(5*11)+1/(7*11)=1/5*S(7,11)+1/7*S(11,11)

The case m=n-1 is then the claim A(n,n-1)>A(n,n-2).
$$A(n,n-1)=S(p_1,p_n)$$
$$A(n,n-2) = \sum_{i=1}^{i=n-1} \frac{1}{p_i} S(p_{i+1},p_n)$$

Divide the set of primes into sets with a reciprocal sum of more than 1, e.g. 1/5+1/7+1/11+...+1/109 > 1 leads to the first block, 1/(113) + 1/... +1/whatever > 1 leads to the primes of the second block and so on. Let's call p_a,b the b'th prime of block a.
As all the blocks end with primes above 10, we also know that the sum of inverse primes in each block is smaller than 1.1.

For A(n,n-2) we form products of pairs of inverse primes. Among them, if n is sufficiently large, we'll find blocks like $$\frac{1}{p_{1,1}p_{2,1}} + \frac{1}{p_{1,1}p_{2,2}}+ \dots + \frac{1}{p_{1,2}p_{2,1}} + \frac{1}{p_{1,2}p_{2,2}}+ \dots \\= \frac{1}{p_{1,1}} \sum_{i=1}^{i_{max}} \frac{1}{p_{2,i}} + \frac{1}{p_{1,2}} \sum_{i=1}^{i_{max}} \frac{1}{p_{2,i}} \\> \sum_{j=1}^{j_{max}} \frac{1}{p_{1,j}} > 1$$
In other words, the products coming from such a block combination add up to more than 1.

Let's consider n such that the primes cover the first 4 blocks. Then A(n,n-1)<4.4, but A(n,n-2) >6 because we have the block combinations (1,2), (1,3), (1,4), (2,3), (2,4) and (3,4).

=> it is not valid for m=n-1 either.

Using similar arguments, you can show that it is valid for no m.

 

[JFGariepy]

Using similar arguments, you can show that it is valid for no m.

Brilliant! You are so much better than me it is both helpful and shameful at the same time. This means I have to reformulate my statement of the problem. I'm quite convinced that what I'm after is true, but I haven't been completely honest in my original post. For your curiosity, and if you are willing to grace me with more of your help, what I was really after is:

Prove that for any n, The following additions/subtraction leads to a result greater than zero:

(first line is positive with m = n and each term contains n Ps)
+ P₁P₂...P_n

(second line is negative with m = n-1 and each term contains n-1 Ps)
- P₁P₂...P_n-1 - P₁P₂...P_n - ...

(third line is positive but multiplied by 2 with m = n-2 and each term contains n-2 Ps)
+ 2(P₁P₂...P_n-2 + P₁P₂...P_n-1 + P₁P₂...P_n + ...)

(fourth line is negative but multiplied by 2 with m = n-3 and each term contains n-3 Ps)
- 2(P₁P₂...P_n-3 + P₁P₂...P_n-2 + P₁P₂...P_n-1 + P₁P₂...P_n + ...)

(each line after that simply alternates between - and + and is also multiplied by 2 all the time while m diminishes 1 by 1)
...

(second to last line negative, with m = 2 and each term containing 2 Ps, also multipled by 2)
+ 2 (P₁P₂ + P₁P₃ + ...)

(last line m = 1, each term containing 1 P, also multiplied by 2)
- 2 (P₁ + P₂ + ...)

(and very last line)
+ 2

The reason I formulated the problem differently in the original post is that I was convinced that the - lines were always smaller than the + lines!

 

[JFGariepy]

So I've used your approach empirically (that is, divide all lines by all primes in the set) and I have moved the "1" that resulted to the left side of the equation so we have:

1 > 1/P₁ + 1/P₂ + 1/P₃ ...
- 2/(P₁P₂) - 2/(P₁P₃) ...
+ 2/(P₁P₂P₃) ...
- 2/(P₁P₂P₃P₄) ...

and I just wanted to show you the results empirically, for the first 21 primes. It seems like it will never reach 1 unless something surprising happens. So the question is whether we can prove that it's converging below one, or that it is not converging but that it is constantly decreasing and never going back toward 1. The Y axis shows the sum of the right hand side of the inequality.

 

[JFGariepy]

I'm attaching here the Matlab code used to generate the previous figure in case someone wants to reproduce the empirical algorithm. It's currently going very slow because I use the function nchoosek, there is probably much faster available.

n = 87;

SumsData = [];
PrimesOriginal = 5:n;
PrimesOriginal = PrimesOriginal(isprime(PrimesOriginal));

for i=2:length(PrimesOriginal),
    i,
    Primes = PrimesOriginal(1:i);
    Sum = 0;
    OneOrTwo = 1;
    Sign = -1;
    for z=1:length(Primes),
        Sign = Sign*-1;
        if z == 2,
            OneOrTwo = 2;
        end
        Temp = nchoosek(Primes,z);
        for j=1:size(Temp,1),
            Sum = Sum + Sign*(OneOrTwo/(prod(Temp(j,:))));
        end
    end
    SumsData(i) = Sum;
end

figure;plot(SumsData);

 

[mfb]

Where does the new expression come from?
If you stop after 4 elements, it will go to negative infinity. If you always consider all those terms up to n as the code suggests, the question becomes more interesting.

 

[JFGariepy]

Where does the new expression come from?
If you stop after 4 elements, it will go to negative infinity. If you always consider all those terms up to n as the code suggests, the question becomes more interesting.

Definitely, the illustration of the case of 4 is simply because I have a hard time expressing it in general terms but yes, the system grows with n and I certainly do not limit the question to 4 lines. The question I ask is whether or not SumsData(i) will remain below 1 at all times as i goes to infinity. And a cleaner, more general representation of the inequality would be:

1 > 1/P₁ + 1/P₂ ... + 1/P_n
- 2/(P₁P₂) - 2/(P₁P₃) ... - 2/(P_n-1P_n)
...
...
- 2/(P₁P₂...P_n-1P_n)

(note that for odd number of lines the line finishes with a - whereas for even number of lines it would finish with a +)

This formulation of the problem comes from the actual problem as I am facing it. This is a missing piece of the puzzle in imposing a boundary on prime densities of certain types of primes for me which is needed as part of an on-going attempt to prove the Goldbach conjecture.