Re: How to prove some inequality?

On Mon, 22 Sep 2008 17:52:59 +0100, I wrote:

[...] I'm having trouble translating it into combinatorial terms.
[...]

In the ring Z[p, q], consider the polynomial (p + q)^{mn} =
((p + q)^m)^n = ((p + q)^n)^m.

Write (p + q)^m = p^m + qF(p, q), and (p + q)^n = q^n + pG(p, q),
where F and G are polynomials with positive integer coefficients.

(BTW, ignore what I wrote later about "G(p, q) = F(q, p)". I was
confusing m and n. A notation like F_n(p, q) would make sense of
it, but it's messy and overelaborate.)

(p + q)^{mn} can be written as a sum of 2^{mn} products of p's
and q's. Index the positions of the p's and q's by a pair of
integers (i, j), where i runs from 1 to m and j runs from 1 to n.

(Think of an mxn array of Bernoulli trials - if that's the correct
term from probability theory.)

For each of the 2^{mn} products, either: (i) for all j, there is a
q in position (i, j) for some i; or (ii) for all i, there is a p in
position (i, j) for some j.

(For, if (i) is false, then there is a j such that there is a p in
position (i, j) for all i, therefore (ii) is true. This argument
seems a bit reminiscent of Koenig's lemma.)

Therefore either the product occurs in the expansion of (qF(p, q))^n
or else it occurs in the expansion of (pG(p, q))^m. Therefore, all
the coefficients of monomials in the polynomial:

(qF(p, q))^n + (pG(p, q))^m

are >= the corresponding coefficients of monomials in (p + q)^{mn}.

[...]

That almost seems to make sense now ...

Almost! I don't know what anyone else thinks, and I don't know if it's
just because I'm tired, but the argument still seems to make less sense
than I'd like it to. (Never mind the more general form, which is simply
longer and messier, but doesn't involve any different ideas.)

It almost makes sense, if you think of F(p, q) as a sum of strings of
concatenated p's and q's, written almost as if multiplication were not
commutative.

For instance, if m = 3, F(p, q) = ppq + pqp + pqq + qpp + qpq + qqp +
qqq. Or at least, /something/ like that - but that vagueness is the
whole problem.

I still don't know what mathematical structure I'm working in. Saying
it was "Z[p, q]" was just a stopgap, a knowingly confused suggestion
of something vaguely related to what it might really be.

Having had hours more to think about it, at odd moments, I'm embarrassed
to report that I still don't know exactly what I was trying to say - in
proper mathematical terms, even though the argument seems sort of valid
in some vague way.

How should I have expressed what I meant about the "positions" of the
letters 'p' and 'q', in terms of an "expansion" of an expression like
(p + q)^{mn}, or (qF(p, q))^n? It seems as if it ought to be utterly
trivial and obvious - but I'm still horribly hazy about it.

For instance, if m = n = 2 (a case, incidentally, when the inequality
is quite easily proved by rewriting (1 - x^2)2 + (1 - y^2)^2 as 1 +
2x^2y^2), we want to be able to write something like (p + q)^4 =
pppp + pppq + ... + qqqq, and ((p + q)^2 - p^2)^2 = (pq + qp + qq)^2,
and ((p + q)^2 - q^2)^2 = (pp + pq + qp)^2, and show that when these
latter two expressions are expanded, with all the p's and q's somehow
arranged in the right "positions", you get an expansion containing
more terms than that of (p + q)^4.

So how do I formalise the idea of using the commutativity of
multiplication to move the p's and q's around into the needed
"positions", while /avoiding/ collecting equal products (i.e.,
monomials in p and q) into terms of a polynomial with positive
integer coefficients? We somehow need to maintain the separate
identity of these "products" of p's and q's (or of x's and y's -
which of course, with hindsight, would have been a better choice).

I would like to be able to think of the products of p's and q's as
somehow being arranged in mxn arrays (which of course is how I
originally conceived of this whole semi-nonsensical thing) - but
how can one sensibly do algebra on such "arrays" of letters?

If you could do such "algebra", I would seem to need it to look,
not like "(p + q)^4 = pppp + ...", but something more like this:

(p+q)(p+q) = pp + pp + pp + pp + pq + pq + pq + pq + qp + qp
(p+q)(p+q) pp pq qp qq pp pq qp qq pp pq

+ qp + qp + qq + qq + qq + qq
qp qq pp pq qp qq

(= a crazy "2D" representation of (p + q)^4)

(pp + pq + qp) = pp + pp + pp + pq + pq + pq + qp + qp + qp
*(pp + pq + qp) pp pq qp pp pq qp pp pq qp

(= a "row" representation of ((p + q)^2 - q^2)^2)

( (
p p
q q
+ +
q * q = pp + pq + pq + qp + qq + qq + qp + qq + qq
p p qq qp qq pq pp pq qq qp qq
+ +
q q
q q
) )

(= an ugly "column" representation of ((p + q)^2 - p^2)^2)

But it's hard to imagine what the laws of such an "algebra"
could be. It presumably has something to do with set theory
and Cartesian products (which I do tend to get cranky about).

Perhaps it just boils down to a poorly-thought-out visual
matrix display of sets of functions {1, 2} x {1, 2} -> {p, q}?

However, I have for a long time seriously thought that there
is something amiss with the way in which the language of the
Cartesian product is necessarily abused so as to make it appear
to be conveniently associative (even though I freely engaged in
such abuse of set-theoretic language myself, in my followup post
concerning the "p-dimensional" generalisation of the inequality).

I think perhaps I need Newton or Professor Moriarty to lend a hand!
Or perhaps James Harris would oblige? (It's only algebra!) :-)

Is this just some really obviously well-known thing, which I'm
unaccountably obfuscating and failing to recognise as something
familiar and simple (as opposed to merely pretending that it's
a familiar and simple manipulation of polynomials in Z[p, q])?

And is it finally time for me to join JSH in the sci.math funny
farm? 8-P

Anyway, if there is some sane mathematical way of making sense
of this, such that the letters in these expressions have fixed
"positions", the "multiplication" involved (surely something to
do with the Cartesian product, but what exactly?) does not have
to be thought of as "commutative". The letters p and q don't
"move around" at all. However, in order to be able finally to
arrive at the desired inequality, we /do/ have to be able somehow
to map these expressions to polynomials, which can be interpreted
as belonging to Z[p, q]. (So we need some kind of "lift" to the
appropriate mathematical structure, but I'm still hopelessly vague
as to what this is.) And then finally p and q can be substituted,
becoming replaced by honest-to-goodness nonnegative real numbers.

By the way, has anyone yet checked the truth of the inequality:

(1 - (y+z)^{mn})^l + (1 - (z+x)^{nl})^m + (1 - (x+y)^{lm})^n >= 1

where x >= 0, y >= 0, z >= 0, x + y + z = 1, and l, m, and n are
positive integers? This seems to follow from the 3D version of
this so-called argument and might provide a check on its sanity.

--
Angus Rodgers
(twirlip@ eats spam; reply to angusrod@)
Contains mild peril
.

Relevant Pages

  • Re: once quasi asked about unions of sets ...
    ... multivariate, with integer coefficients, could have as its range ... the union of the set of multiples of 2 and the ... consider m-variate polynomials h with integer coefficients such that h ...
    (sci.math)
  • Re: Exact (LISP-ish) calculations in Ruby?
    ... polynomials are definitely where it's easy -- I wrote something to ... messy library for handling mathematical expressions. ... messy object model to hold the expressions, ... reasonable representation. ...
    (comp.lang.ruby)
  • Re: JSH: Stolen dreams and the distributive property
    ... Skip the polemic, let's see the math. ... polynomial with integer coefficients, ... f_1 and f_2 are not polynomials, ... everything in sight lives in some big ring. ...
    (sci.math)
  • Re: all prime factors of f(n) are mutually congruent mod m
    ... polynomial f with integer coefficients such that, for all integers n, ... all prime factors of fare congruent to 1 mod 3. ... all polynomials falso have this property ... including that the norm group of ideals ...
    (sci.math)
  • Re: all prime factors of f(n) are mutually congruent mod m
    ... polynomial f with integer coefficients such that, for all integers n, ... all prime factors of fare congruent to 1 mod 3. ... used to construct polynomials (find a monic one and kill ... including that the norm group of ideals ...
    (sci.math)
Quantcast