5
$\begingroup$

Given an integer $n\in\Bbb N$, what's the best (known) way to decompose it as the product of two integers in such a way that the factors are the sides of a rectangle that's as close as possible to a square? The full factorization of $n$ into prime factors can be assumed to be known if that's helpful.

More formally:

Given $n\in \Bbb N$, find a divisor $d|n$ such that $ |d-n/d| \stackrel{!}= \min$.

or

Given $n\in \Bbb N$, find $a, b\in\Bbb N$ such that $a\cdot b=n$ and $a+b \stackrel{!}= \min$.

Using the factorization $n = \displaystyle \prod_{j=1}^k p_j$ where primes might occur more than once, this can be restated using logarithms:

Find $k$ values $b_j\in\{-1,1\}$ such that $\displaystyle \Bigg|\sum_{j=1}^k b_j\log p_j \Bigg|\stackrel{!}= \min$.

This looks like a knapsack problem which are known to be hard in general. For $n > 1$ there are $2^{k-1}$ possible decompositions into different pairs of factors, and checking all of them is expensive when $n$ has many factors. Moreover:

If someone comes up with a specific decomposition asserting it's the most square-ish one: Is it easier to check whether the solution is correct, or is it as expensive as determining the best solution in the first place?

As an example, let $H_D(x)\in \Bbb Z[x]$ be the Hilbert class polynomial for discriminant $D$ and let $n=H_{-71}(0)$: $$n = 737707086760731113357714241006081263 = 11^9 \cdot 17^6 \cdot 23^3 \cdot 41^3 \cdot 47^3 \cdot 53^3$$

See [1]. This $n$ has $2^{26} = 67\,108\,864$ different decompositions, which is doable with brute force on a modern computer. But is there a smarter approach?

Two more demanding test cases are

  • $H_{-119}(0) = (11^4 \cdot 17 \cdot 23^2 \cdot 29^2 \cdot 47 \cdot 59 \cdot 83 \cdot 89)^3$ with $2^{38}\approx 2.7\cdot 10^{11}$ decompositions and

  • $H_{-907}(0) = (2^{19} \cdot 3^3 \cdot 5^3 \cdot 131 \cdot 137 \cdot 167)^3$ with $2^{83}\approx 9.7\cdot 10^{24}$ decompositions.

Note 1

As Jukka Kohonen mentions in a comment, the upper bound for the complexity of a brute-force approach can be reduced: Let $n=\displaystyle\prod_{i=1}^m p_i^{e_i}$ with pairwise different primes $p_i$ be the factorization of $n$. Then the task is:

Find $m$ integers $a_i$ with $0\leqslant a_i \leqslant e_i$ such that $\Bigg|\log n - 2\displaystyle \sum_{i=1}^m a_i\log p_i \Bigg| \stackrel!= \min$.

If all $a_i$ are replaced by $e_i-a_i$ then the value to be minimized stays the same.

  1. If all $e_i$ are even, then $n$ is a perfect square and the solution is clear.
  2. If at least one $e_i$ is odd, then a brute-force approach has to test $\dfrac12\displaystyle\prod_{i=1}^m (1+e_i)$ combinations of the $a_i$.

The examples above are all in case 2., and the corrected number of tries are:

  • $H_{-71}(0)$: $\frac12\cdot 10 \cdot 7 \cdot 4 \cdot 4 \cdot 4 \cdot 4 = 8960$ possibilities.

  • $H_{-119}(0)$: $\frac12\cdot 13 \cdot 4 \cdot 7 \cdot 7 \cdot 4 \cdot 4 \cdot 4 \cdot 4 = 326144$ possibilities.

  • $H_{-907}(0)$: $\frac12\cdot 58 \cdot 10 \cdot 10 \cdot 4 \cdot 4 \cdot 4 = 185600$ possibilities.

Conclusion:

The work that's needed to get the complete factorization of $n$ is in general much higher than brute-force checking which pair of divisors is the best choice.

Related:

$\endgroup$
5
  • 3
    $\begingroup$ I think you are slightly overestimating the brute force workload. Given $n=11^9 \cdot 17^6 \cdot 23^3 \cdot 41^3 \cdot 47^3 \cdot 53^3 = ab$, you want to divide the nine 11's between the factors (10 choices), same for the six 17's (7 choices) etc. so $10 \cdot 7 \cdot 4 \cdot 4 \cdot 4 \cdot 4 = 17920$ decompositions, not $67108864$. (And divide by two because you can assume $a$ has fewer 11's than $b$.) $\endgroup$
    – Jukka Kohonen
    Sep 7, 2021 at 10:50
  • $\begingroup$ @Jukka Kohonen: You are right, thanks. I will edit my question, but it will take some hours til I'm back. $\endgroup$
    – emacs drives me nuts
    Sep 7, 2021 at 11:22
  • 2
    $\begingroup$ Ok. For the record, the most-square factorization for $H_{-907}(0)$ seems to be $386208961375062977740800 \cdot 386219092937277440000000$, by brute-force SageMath code in 23 seconds, so you'll want to create more demanding test cases. $\endgroup$
    – Jukka Kohonen
    Sep 7, 2021 at 11:33
  • 1
    $\begingroup$ As long as we can enumerate over the divisors of the given number, the problem can be done by brute force. And I highly doubt that there is a better method in general. Note that you do not need to enumerate all decompositions. It is sufficient to know all the divisors. Your last example still has only $371\ 200$ divisors. This is no challenge whatsoever. $\endgroup$
    – Peter
    Sep 7, 2021 at 13:38
  • 1
    $\begingroup$ In fact the first $H$ is a harder instance, but still far from being a challenge. $\endgroup$
    – Peter
    Sep 7, 2021 at 13:46

1 Answer 1

Reset to default
2
$\begingroup$

Equivalently, you want to minimize the larger of the two factors. Given the prime factorization $\prod_{i=1}^m p_i^{e_i}$, you can solve the problem via integer linear programming as follows. Let integer decision variable $x_i$ denote the number of times that $p_i$ appears in the first factor, so that the two factors are $\prod_{i=1}^m p_i^{x_i}$ and $\prod_{i=1}^m p_i^{e_i-x_i}$. The problem is to minimize $z$ subject to \begin{align} \sum_{i=1}^m \log(p_i) x_i &\le z \tag1 \\ \sum_{i=1}^m \log(p_i) (e_i-x_i) &\le z \tag2 \\ 0 \le x_i &\le e_i &&\text{for $i\in\{1,\dots,m\}$} \tag3 \end{align} Constraints $(1)$ and $(2)$ enforce the minimax objective. Constraint $(3)$ enforces the factorization.

All three test cases solve instantly. For the third one, an optimal solution is $x=(16, 9, 2, 0, 3, 3)$, which agrees with @Jukka Kohonen.

$\endgroup$

You must log in to answer this question.

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