# On the complexity of factorial ratios

Given two polynomials $$p(x_1,\dots,x_n)\in\mathbb Z[x_1,\dots,x_n]$$ and $$q(y_1,\dots,y_m)\in\mathbb Z[y_1,\dots,y_m]$$ and $$n+m$$ positive integers $$a_1,\dots,a_n,b_1,\dots,b_m$$ where:

1. degree of the polynomials

2. number of bits in coefficients of the polynomials

3. the number of bits in integers $$a_i$$

4. the number of bits in integers $$b_j$$

5. $$n,m$$

are all polynomial in $$t$$ (a parameter).

The problem is to decide if

$$\frac{p(a_1!,\dots,a_n!)}{q(b_1!,\dots,b_m!)}$$

is an integer.

1. Is the problem in time complexity $$O(poly(t))$$ in worst case scenario?

2. What is the complexity class in which the problem lies in?

• Can you evaluate the numerator & denominator in polynomial time? If you can, then you can apply Euclid's algorithm to work out whether the quotient is an integer. May 23 at 7:24
• Corrected the mistake.
– Mr.
May 23 at 8:19
• A very special case of this problem is to determine if $\frac{(p-1)!+1}{p}$ is an integer, which is equivalent to $p$ being prime. Of course this is known to be polynomial-time solvable, but is already very nontrivial. I doubt much is known in the general case. May 23 at 13:08

I claim that there is an algorithm for factorizing integers that runs in polynomial time if it has access to an oracle that states whether $$\frac{p(a_{1}!,\dots,a_{n}!)}{q(b_{1}!,\dots,b_{n}!)}$$ is an integer or not.
Suppose that $$x$$ is a positive integer that one seeks to factorize. Wilson's theorem states that $$x$$ is prime if and only if $$(x-1)!=-1\bmod x$$. Using Wilson's theorem, this oracle can determine whether $$x$$ is a prime number or not. Primality testing runs in polynomial time so we don't even need Wilson's theorem. If $$x$$ is a composite number, then one can use this algorithm to return a factor of $$x$$ that is not $$1$$ or $$x$$ using the following technique. By repeatedly using the oracle, one first finds the least natural number $$n$$ such that $$x$$ is a factor of $$n!$$. The process of finding the number $$n$$ requires one to access the oracle $$O(\mathsf{log}(n))$$ many times. Therefore, since $$x$$ is a factor of $$n!$$ but $$x$$ is not a factor of $$(n-1)!$$, we know that $$n$$ and $$x$$ have a common factor, so we compute $$\mathsf{gcd}(x,n)$$.
There are no known polynomial time factorization algorithms. Since the security of many cryptographic algorithms depends on the fact that factorization is difficult, we know that people are confident that there is probably not a polynomial time factorization algorithm, so I doubt that the problem of determining whether $$\frac{p(a_{1}!,\dots,a_{n}!)}{q(b_{1}!,\dots,b_{n}!)}$$ is an integer or not is in polynomial time. However, since factorization lies in BQP (the analogue of P for quantum computation), this answer does not preclude the problem of determining whether $$\frac{p(a_{1}!,\dots,a_{n}!)}{q(b_{1}!,\dots,b_{n}!)}$$ is an integer lies in $$\mathsf{BQP}$$.