Repository: sympy/sympy
Pull request: Improvement_of_dup_zz_mignotte_bound(f, K)
So, this is our change in the `dup_zz_mignotte_bound(f, K)` method. Also, we have replace the old value in the test_factortools.py file. If it is asked, we can cite our test_file with the comparison of the bounds. As it was mentioned, we have not create a new method but just change the code in the `dup_zz_mignotte_bound(f, K)`.


Fixes #19253 
<!-- Your title above should be a short description of what
was changed. Do not include the issue number in the title. -->

#### References to other Issues or PRs
<!-- If this pull request fixes an issue, write "Fixes #NNNN" in that exact
format, e.g. "Fixes #1234" (see
https://tinyurl.com/auto-closing for more information). Also, please
write a comment on that issue linking back to this pull request once it is
open. -->


#### Brief description of what is fixed or changed
`dup_zz_mignotte_bound(f, K)` implemented with Knuth-Cohen

#### Other comments
As it was mentioned in the issue, `dmp_zz_mignotte_bound(f, u, K)` should also be cared of.


#### Release Notes

<!-- Write the release notes for this release below. See
https://github.com/sympy/sympy/wiki/Writing-Release-Notes for more information
on how to write release notes. The bot will check your release notes
automatically to see if they are formatted correctly. -->

<!-- BEGIN RELEASE NOTES -->
* polys
    * improvement of `dup_zz_mignotte_bound(f, K)` by Knuth-Cohen bound
<!-- END RELEASE NOTES -->

Problem statement:
sympy.polys.factortools.dmp_zz_mignotte_bound improvement
The method `dup_zz_mignotte_bound(f, K)` can be significantly improved by using the **Knuth-Cohen bound** instead. After our research with Prof. Ag.Akritas we have implemented the Knuth-Cohen bound among others, and compare them among dozens of polynomials with different degree, density and coefficients range. Considering the results and the feedback from Mr.Kalevi Suominen, our proposal is that the mignotte_bound should be replaced by the knuth-cohen bound.
Also, `dmp_zz_mignotte_bound(f, u, K)` for mutli-variants polynomials should be replaced appropriately.

Hints from issue discussion:

Commit message: 19253_Replacement_of_dup_zz_mignotte_bound(f, K)

So, this is our change in the `dup_zz_mignotte_bound(f, K)` method. Also, we have replace the old value in the test_factortools.py file. If it is asked, we can cite our test_file with the comparison of the bounds.

Patch to review:
diff --git a/sympy/polys/factortools.py b/sympy/polys/factortools.py
index 93298f47e671..99b754382a9e 100644
--- a/sympy/polys/factortools.py
+++ b/sympy/polys/factortools.py
@@ -124,13 +124,29 @@ def dmp_trial_division(f, factors, u, K):
 
 
 def dup_zz_mignotte_bound(f, K):
-    """Mignotte bound for univariate polynomials in `K[x]`. """
-    a = dup_max_norm(f, K)
-    b = abs(dup_LC(f, K))
-    n = dup_degree(f)
-
-    return K.sqrt(K(n + 1))*2**n*a*b
+    """
+    The Knuth-Cohen variant of Mignotte bound for
+    univariate polynomials in `K[x]`.
 
+    Reference: John Abbott, Journal of Symbolic Computation 50 (2013) 532–563.
+    """
+    d = dup_degree(f)
+    delta = _ceil( d / 2 )
+    
+    # euclidean-norm
+    eucl_norm = K.sqrt( sum( [cf**2 for cf in f] ) )
+
+    # biggest values of binomial coefficients (p. 538 of reference)
+    t1 = binomial( delta - 1, _ceil( delta / 2 ) )
+    t2 = binomial( delta - 1, _ceil( delta / 2 ) - 1 )
+
+    lc = abs( dup_LC(f, K) )   # leading coefficient
+    
+    bound = t1 * eucl_norm + t2 * lc   # (p. 538 of reference)
+    
+    bound = _ceil( bound / 2 ) * 2   # round up to even integer
+    
+    return bound + dup_max_norm(f, K)  # add max_coeff for irreducible polys
 
 def dmp_zz_mignotte_bound(f, u, K):
     """Mignotte bound for multivariate polynomials in `K[X]`. """
@@ -1147,7 +1163,7 @@ def dmp_ext_factor(f, u, K):
         return lc, []
 
     f, F = dmp_sqf_part(f, u, K), f
-    s, g, r = dmp_sqf_norm(F, u, K)
+    s, g, r = dmp_sqf_norm(f, u, K)
 
     factors = dmp_factor_list_include(r, u, K.dom)
 
diff --git a/sympy/polys/tests/test_factortools.py b/sympy/polys/tests/test_factortools.py
index 7bcd9357569a..77524e43deff 100644
--- a/sympy/polys/tests/test_factortools.py
+++ b/sympy/polys/tests/test_factortools.py
@@ -27,7 +27,7 @@ def test_dmp_trial_division():
 
 def test_dup_zz_mignotte_bound():
     R, x = ring("x", ZZ)
-    assert R.dup_zz_mignotte_bound(2*x**2 + 3*x + 4) == 32
+    assert R.dup_zz_mignotte_bound(2*x**2 + 3*x + 4) == 6
 
 
 def test_dmp_zz_mignotte_bound():


Code review comments:
diff_hunk: @@ -124,13 +124,29 @@ def dmp_trial_division(f, factors, u, K):
 
 
 def dup_zz_mignotte_bound(f, K):
-    """Mignotte bound for univariate polynomials in `K[x]`. """
-    a = dup_max_norm(f, K)
-    b = abs(dup_LC(f, K))
-    n = dup_degree(f)
-
-    return K.sqrt(K(n + 1))*2**n*a*b
+    """
+    The Knuth-Cohen variant of Mignotte bound for
+    univariate polynomials in `K[x]`.
 
+    Reference: John Abbott, Journal of Symbolic Computation 50 (2013) 532–563.
+    """
+    d = dup_degree(f)
+    delta = _ceil( d / 2 )
+    
+    # euclidean-norm
+    eucl_norm = K.sqrt( sum( [cf**2 for cf in f] ) )
+
+    # biggest values of binomial coefficients (p. 538 of reference)
+    t1 = binomial( delta - 1, _ceil( delta / 2 ) )
path: sympy/polys/factortools.py
text: @user1:
`binomial` is not defined.

@author:
You are right, checking the log now i see: "ImportError: cannot import name 'binomial' from partially initialized module 'sympy' (most likely due to a circular import)"
What is the correct way of importing the binomial function?

@user2:
If you want to resolve the circular import issue, you should import inside the function block itself.

diff_hunk: @@ -124,13 +124,29 @@ def dmp_trial_division(f, factors, u, K):
 
 
 def dup_zz_mignotte_bound(f, K):
-    """Mignotte bound for univariate polynomials in `K[x]`. """
-    a = dup_max_norm(f, K)
-    b = abs(dup_LC(f, K))
-    n = dup_degree(f)
-
-    return K.sqrt(K(n + 1))*2**n*a*b
+    """
+    The Knuth-Cohen variant of Mignotte bound for
+    univariate polynomials in `K[x]`.
 
+    Reference: John Abbott, Journal of Symbolic Computation 50 (2013) 532–563.
path: sympy/polys/factortools.py
text: @user1:
Please see other methods on how to include references.

@author:
Can you please give me a link with this?

@user1:
Have a look at [references](https://github.com/sympy/sympy/blob/8adfdbed18e6a0e06d862213752d2cb96a84218a/sympy/polys/factortools.py#L182)

@author:
Think i got it right!