# Integer minimization problem: products of (powers minus one)

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?

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.

• 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? Commented Sep 20, 2019 at 15:59
• 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. Commented Sep 20, 2019 at 16:10
• Yes, you got there before I could type a reply!
– user502266
Commented Sep 20, 2019 at 16:14