0
$\begingroup$

In my work I have a certain finite set $X(a,n)$ determined by two positive integers $a$ and $n$, each strictly greater than $1$. (The origins of the set and the dependence on $a$ and $n$ are not relevant to my question here.) I need some information on the order of $X(a,n)$ as a function of $n$ for fixed $a$.

I am able to prove that--for fixed $a$--the order of $X(a,n)$ is given by a product of the form $$ (a^{e_1}-1)(a^{e_2}-1) \cdots (a^{e_k}-1) $$ where the exponents $e_i$ satisfy $e_1+e_2+\cdots + e_k=n$, each exponent a positive integer (so no zeros allowed). However, I will not know in general how many summands ($k$) there are nor what the individual exponents will be. I can only get this data on a case-by-case basis, and no general patterns appear.

I have found that if I knew the minimum possible outcome for such an expression, I would be able to prove my ultimate result. This is my question here: is there a way to establish the minimum possible outcome of such a product given the above constraint?

Question: For fixed $a$ and $n$ find $$ \min_{e_1+e_2+\cdots + e_k=n} \ \prod_{i=1}^k (a^{e_i}-1). $$

It "feels like" the min should occur when all $e_i=1$, so the minimum value is just $(a-1)^n$, but I don't see why (even though I think it is not so hard). I've written out some examples and have done some calculations, and the data does not contradict my conjecture.

Conjecture: The minimum value above is $(a-1)^n$, occurring when $e_1 = e_2 = \cdots = e_n=1$.

Example: With $n=4$ we have four possible partitions yielding the following products:

$1 + 1 + 1 + 1 \Rightarrow (a-1)^4$

$1 + 1 + 2 \Rightarrow (a-1)^2(a^2-1)$

$1+3 \Rightarrow (a-1)(a^3-1)$

$2 + 2 \Rightarrow (a^2-1)^2$.

Running various values of $a$ shows that the minimum occurs in the first case every time. You can do the same for other values of $n$ with the same conclusion.

I have a sneaky feeling this is relatively straightforward and I have overlooked something obvious. Is my conjecture on the minimum correct, and if so, what is the argument?

$\endgroup$

1 Answer 1

3
$\begingroup$

Yes, your conjecture is true.

You only need look at two of the variables, $a^e,a^f$, with $e+f$ fixed.

Then $(1-a^e)(1-a^f)=1-a^e-a^f+a^{e+f}$.

We need to maximise $a^e+a^f$. This occurs when $e$ and $f$ are equal.

$\endgroup$
3
  • $\begingroup$ This is helpful to be sure, but I don't think it extends to give the general case. The problem is that $k$ itself is variable. Given $n$, we have to consider this problem for $k =2, 3, \ldots, n$. When $k=n$ your argument modifies by using Lagrange multipliers. However, this does not tell us that the min for the $k=n$ case is still smaller than the min for the cases $k= 2, \ldots, n-1$. Or does it? $\endgroup$
    – Randall
    Commented Sep 20, 2019 at 15:59
  • $\begingroup$ Never mind, I just figured it out. It's as simple as allowing the exponents to be $0$, for then the terms drop out and it's the same Lagrange multiplier problem. $\endgroup$
    – Randall
    Commented Sep 20, 2019 at 16:10
  • 1
    $\begingroup$ Yes, you got there before I could type a reply! $\endgroup$
    – user502266
    Commented Sep 20, 2019 at 16:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .