Re: Possible results from three variables

quasi <quasi@xxxxxxxx> writes:

On Thu, 12 Jul 2007 19:23:59 -0500, Robert Israel
<israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

quasi <quasi@xxxxxxxx> writes:

On Thu, 12 Jul 2007 07:25:37 -0000, "bakpao@xxxxxxxxx"
<bakpao@xxxxxxxxx> wrote:

Given three variables, say x, y, z with each variable being an integer
from 1 to 10, how many possible values are there from the equation of
x * y * z? The quickest and incorrect answer is 1000 (from 10x10x10).
This is wrong because some of the combinations actually the same, e.g.
1*2*4 = 1*4*2 = 4*1*2 = 1*8*1. Doing 10C3 is also wrong.

Is there any formula that we can use to find out the number of
possibilities for the different integer range (e.g. 1 - 5 or 1 - 8)?

For positive integers n,k, let f(n,k) be the number of possible
products of k integers from the range 1 to n inclusive.

It's obvious that f(1,k)=1 for all positive integers k.

It's also obvious that f(n,1)=n for all positive integers n,

For a fixed positive integer n, it appears that f(n,k) is always a
polynomial in k.

Very interesting...

You can think of it this way. Suppose p_1, ..., p_m are the primes
<= n. Each possible product can be represented uniquely in the form
y = p_1^y_1 ... p_m^y_m where y_1 ... y_m are nonnegative integers. If
a_{ix} is the power of p_i appearing in the representation of x and
y = 1^{x_1} 2^{x_2} ... n^{x_n} is one of the products we have
p_i = sum_{j=1}^n a_{ij} x_j with sum_{i=1}^n x_i = k. Thus f(n,k) is
the cardinality of T(K_k) where T is the linear map of R^n to R^m
corresponding to the m x n matrix (a_{ij}) and
K_k = {(x_1,...,x_n) in Z^n: all x_i >= 0, sum_i x_i = k}.
Essentially we're trying to count the lattice points in the dilations of a
fixed polytope.
A quick search turns up Ehrhart polynomials
<http://mathworld.wolfram.com/EhrhartPolynomial.html>...

I'm not sure whether your argument above, together with results in the
above link, proves that for all positive integers n, f(n,k) is a
polynomial in k. Does it?

To amplify somewhat:

Since T has integer entries, M = T(Z^n) is a discrete
subgroup of R^m, i.e. a lattice. Let K be the polytope
T({z in R^n: all z_i >= 0, sum_i z_i = 1}). Then
f(n,k) is the cardinality of M intersect (k K). Unless
there's something wrong with the statement of Ehrhart's theorem
in that web page [I haven't checked the original sources], that
should say that f(n,k) is a polynomial, and further that the
degree of the polynomial is the dimension of the lattice M.

In the case at hand, since the primes p_1 to p_m are all in {1,...,n},
the lattice is just Z^m itself. The more general case would be
needed if you replaced {1,...,n} by an arbitrary finite set of positive
integers.

For example, consider n = 4. Then m = 2 with primes p_1 = 2 and p_2 = 3.
K is the convex hull of [0,0], [2,0] and [0,1], a right triangle of area
1, with 4 boundary points on the lattice Z^2. k K has area k^2,
4 k boundary points on the lattice, and, by Pick's theorem,
k^2 - 2 k + 1 interior points on the lattice. Thus
f(4,k) = k^2 + 2 k + 1 = (k+1)^2.
--
Robert Israel israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada V6T 1Z2
.

Relevant Pages

  • Re: Possible results from three variables
    ... For positive integers n,k, let fbe the number of possible ... subgroup of R^m, i.e. a lattice. ... Let K be the polytope ... polynomials in k with rational coefficients. ...
    (sci.math)
  • Re: Possible results from three variables
    ... For positive integers n,k, let fbe the number ... since they have combinatorical meaning in a similar way to the original question here. ... and also some kind of Ehrhart polynomials, but ill stick with euler at first sight. ...
    (sci.math)
  • Re: ranges of integer polynomials
    ... Note that if A is a set of positive integers, ... but have the same recursive ranges ... which of these other, "hyperbolic", polynomials ... This gets at the heart of the undecidability issue. ...
    (sci.math)
  • @quasi : deny "ab + cd"
    ... i was thinking about the set ab + cd with all variables integers>=2. ... the set of positive integers that are the sum of 2 composites. ... suppose we allow polynomials of integer and primevalued variables; then can deny be stated in such a polynomial variant? ...
    (sci.math)
  • Re: Possible results from three variables
    ... A quick search turns up Ehrhart polynomials ... subgroup of R^m, i.e. a lattice. ... needed if you replaced by an arbitrary finite set of positive ... M intersect is Tfor some x in Z^n, ...
    (sci.math)