Binomial of integer (mod n) returns integer

5a86714c-4e74-4458-8b30-320c32c63dfe commented 12 years ago

sage: R = Integers(6)
sage: binomial(R(5), R(2))
10
sage: binomial(R(5), R(2)).parent()
Integer Ring

But binomial(R(5), R(2)) is nonsense, both as an element of ZZ and as an element of R:

sage: binomial(5, 2)
10
sage: binomial(11, 2)
55
sage: binomial(5, 8)
0

On input binomial(x, y), what Sage should do instead is the following:

If the parent of y is Zmod(n) rather than ZZ, a TypeError should be raised.
(This seems to be fixed by #17852) If factorial(y) is zero or a zero-divisor in the parent of x, a ZeroDivisionError should be raised. This is automatic if one computes binomial(x, y) simply as
```
x.parent()(prod([x-k for k in range(y)]) / factorial(y))
```

Apply:

attachment: 12179_new.patch

Component: basic arithmetic

Keywords: binomial coefficient modulo sd35

Stopgaps: todo

Author: Sam Scott, Marco Streng

Reviewer: Colton Pauderis, Johan Bosman, Marco Streng

Issue created by migration from https://trac.sagemath.org/ticket/12179

5a86714c-4e74-4458-8b30-320c32c63dfe commented 12 years ago

Attachment: 12179.patch.gz

5a86714c-4e74-4458-8b30-320c32c63dfe commented 12 years ago

comment:1

Attached patch should add this functionality with no impact on speed of standard integer/float/etc binomial calculation.

7c0f48b0-ea40-4815-970b-1841c816f261 commented 12 years ago

comment:2

Looks good to me: positive review.

5a86714c-4e74-4458-8b30-320c32c63dfe commented 12 years ago

Author: Sam Scott

5a86714c-4e74-4458-8b30-320c32c63dfe commented 12 years ago

comment:4

Attachment: 12179.2.patch.gz

Patch added to deal with the case where the input was a primitive python int.

Thanks to Colton (cpauderis) for catching that one.

1659f18b-8e7f-4ace-87e0-ea435f3ce618 commented 12 years ago

comment:5

The line

 Test of integers modulo n:
}}{
should end in two colons (for docbuilding).  Furthermore, 
{{{
 return x.parent()(binomial(ZZ(x), m, **kwds)) 
}}}
is inefficient when computing modulo a small number n: the binomial coefficient over ZZ may be huge, whereas its reduction modulo n will be small.  It is therefore better to to the entire calculation modulo n.

1659f18b-8e7f-4ace-87e0-ea435f3ce618 commented 12 years ago

comment:6

The line

 Test of integers modulo n:

should end in two colons (for docbuilding). Furthermore,

 return x.parent()(binomial(ZZ(x), m, **kwds))

is inefficient when computing modulo a small number n: the binomial coefficient over ZZ may be huge, whereas its reduction modulo n will be small. It is therefore better to to the entire calculation modulo n.

1659f18b-8e7f-4ace-87e0-ea435f3ce618 commented 12 years ago

Changed keywords from binomial coefficiant, modulo to binomial coefficiant, modulo sd35

mstreng commented 12 years ago

Work Issues: rebase on top of #11417, reST formatting issue, improve efficiency

mstreng commented 12 years ago

comment:8

Patch is incompatible with #11417, which is already merged.

mstreng commented 12 years ago

Reviewer: Colton Pauderis, Johan Bosman, Marco Streng

mstreng commented 12 years ago

Dependencies: #11417

mstreng commented 12 years ago

Changed keywords from binomial coefficiant, modulo sd35 to binomial coefficient modulo sd35

5a86714c-4e74-4458-8b30-320c32c63dfe commented 12 years ago

comment:9

Replying to @sagetrac-johanbosman:

Furthermore,
 return x.parent()(binomial(ZZ(x), m, **kwds)) 
is inefficient when computing modulo a small number n: the binomial coefficient over ZZ may be huge, whereas its reduction modulo n will be small. It is therefore better to to the entire calculation modulo n.

I definitely agree, the changes I was proposing were to simply try and return a more sensible type.

Since I am new to sage, I was trying to keep as much of the existing algorithm intact, so that it wouldn't have any unexpected behaviour. For example, currently it seems that sage uses Peri to calculate the usual binomial coefficient. So I wasn't sure if the implementation for modulo n would belong here.

5a86714c-4e74-4458-8b30-320c32c63dfe commented 12 years ago

comment:10

That should obviously be Pari, not Peri.

mstreng commented 12 years ago

comment:11

Replying to @sagetrac-scotts:

I definitely agree, the changes I was proposing were to simply try and return a more sensible type.

Since I am new to sage, I was trying to keep as much of the existing algorithm intact, so that it wouldn't have any unexpected behaviour. For example, currently it seems that sage uses Peri to calculate the usual binomial coefficient. So I wasn't sure if the implementation for modulo n would belong here.

That sounds sensible, this is a bugfix patch and the inefficiency is not introduced by your patch. So if you don't want to, you don't have to improve the speed. However, since you're editing anyway, you might as well. It's up to you. The other issues

documentation that does not build correctly
a conflicting patch has already been merged

do need to be resolved though.

For the first issue, after building Sage, use sage -docbuild reference html to rebuild the documentation and see if all the changed documentation looks good (in this case, replacing : by :: will probably be enough).

As for the second issue, you should not write two independent patches editing the same part of a file. They can't be applied after each other, because the second-to-be-applied can't find the piece of code that it should change. You should write your patch for #12179 on top of a copy of Sage that has #11417 applied.

5a86714c-4e74-4458-8b30-320c32c63dfe commented 11 years ago

Attachment: 12179.3.patch.gz

5a86714c-4e74-4458-8b30-320c32c63dfe commented 11 years ago

comment:12

Finally got around to reinstalling sage after a hard-drive failure. Hoping to get back on track with contributing to sage. Sorry for the incredibly slow response.

Hopefully this should tie up this loose end.

While I do agree that there is room for improving the speed of calculating binomial coefficients mod N, I don't feel like it's worth bloating the binomial function with multiple extra lines of code for something which doesn't seem to be used much.

Perhaps it could be added as a feature at a later stage when the need is there.

However, I feel that this patch adequately addresses the original issue: that elements are treated as integers and returned as such, with no attempt to return them to their original class. This could potentially help with other cases.

Thanks for the advice with regards to the other issues.

mstreng commented 11 years ago

Description changed:

--- 
+++ 
@@ -7,8 +7,21 @@
 Integer Ring

-Wouldn't we expect the answer to be 4 and an element of R? +But binomial(R(5), R(2)) is nonsense, both as an element of ZZ and as an element of R:

+ +sage: binomial(5, 2) +10 +sage: binomial(11, 2) +55 +sage: binomial(5, 8) +0 +

-The offending code is in the method binomial of rings/arith.py -The problem is that the code will immediately attempt to deal with the inputs as integers by x=ZZ(x) and makes no attempt to convert them back into the original ring. +On input binomial(x, y), what Sage should do instead is the following: + If the parent of y is Zmod(n) rather than ZZ, a ValueError should be raised. + If factorial(y) is zero or a zero-divisor in the parent of x, a ZeroDivisionError should be raised. This is automatic if one computes binomial(x, y) simply as +

x.parent(prod([x-k for k in range(y)]) / factorial(y))

mstreng commented 11 years ago

comment:13

Oops, I never got around to looking at the mathematics while reviewing your rest-formatting before. The problem is that binomial(x, y) is in general not defined for x and y integers modulo n. I'll update the ticket description appropriately.

Allowing y to be anything other than an integer makes no sense to me. What would the definition be? In any case, the output has to be in the ring containing x, and will definitely depend on the exact integer y, and not just on y modulo any n. For example:

sage: binomial(5,-2) # bionomial(5, Zmod(2)(0)) = ???
0
sage: binomial(5,0)
1
sage: binomial(5,2)
10
sage: binomial(5,4) 
5
sage: binomial(5,6)
0

Summary: if y is an element of Zmod(n), then surely a ValueError must be raised.

The situation when x is an element of Zmod(n) is more complicated, but cannot be always automatically allowed:

sage: binomial(1, 3) % 3 # binomial(Zmod(3)(1), 3) = ???
0
sage: binomial(4, 3) % 3
1
sage: binomial(7, 3) % 3
2

So the correct answer to binomial(Zmod(3)(1), 3) is "any integer modulo 3". Just returning Zmod(3)(0) is wrong. It would be ok to raise an error, I'd say ZeroDivisionError, because of the following completely general formula:

sage: binomial(x, 3)
1/6*x^3 - 1/2*x^2 + 1/3*x

There are of course some cases that we can still allow. Suppose the input is binomial(Zmod(n)(x), y).

If n is coprime to factorial(y), then all divisions are allowed, so the output should again be a well-defined element of Zmod(n). This is what happens with the code x.parent()(prod([x-k for k in range(y)]) / factorial(y)) from the ticket description.
In general, we could allow the output be an element of Zmod(n / gcd(factorial(y), n)) instead of Zmod(n). This would mean no ZeroDivisionErrors are raised, but Zmod(1)(0) is returned instead. This makes sense in the theory and practice of p-adic power series and formal groups, but may not be what the user expects, so I left this out of the new ticket description.

mstreng commented 11 years ago

Changed work issues from rebase on top of #11417, reST formatting issue, improve efficiency to none

mstreng commented 11 years ago

comment:14

Replying to @mstreng:

Summary: if y is an element of Zmod(n), then surely a ValueError must be raised.

no, wait, I meant TypeError

mstreng commented 11 years ago

Description changed:

--- 
+++ 
@@ -19,7 +19,7 @@

On input binomial(x, y), what Sage should do instead is the following: - If the parent of y is Zmod(n) rather than ZZ, a ValueError should be raised. + If the parent of y is Zmod(n) rather than ZZ, a TypeError should be raised.

If factorial(y) is zero or a zero-divisor in the parent of x, a ZeroDivisionError should be raised. This is automatic if one computes binomial(x, y) simply as

mstreng commented 11 years ago

Description changed:

--- 
+++ 
@@ -23,5 +23,5 @@
 * If factorial(y) is zero or a zero-divisor in the parent of x, a `ZeroDivisionError` should be raised. This is automatic if one computes binomial(x, y) simply as

x.parent(prod([x-k for k in range(y)]) / factorial(y))
x.parent()(prod([x-k for k in range(y)]) / factorial(y))

mstreng commented 11 years ago

Changed dependencies from #11417 to none

mstreng commented 11 years ago

Changed author from Sam Scott to Sam Scott, Marco Streng

mstreng commented 11 years ago

Description changed:

--- 
+++ 
@@ -25,3 +25,7 @@

x.parent()(prod([x-k for k in range(y)]) / factorial(y))

+
+Apply:
+
+* [attachment: 12179_new.patch](https://github.com/sagemath/sage-prod/files/10654340/12179_new.patch.gz)

mstreng commented 11 years ago

comment:16

apply only 12179_new.patch

mstreng commented 11 years ago

comment:17

Attachment: 12179_new.patch.gz

New version, but it screws up lots of symbolic things. Perhaps a few special cases, like binomial(n, n) always returning 1, will fix this. I'm done with this for now.

rwst commented 10 years ago

comment:22

Replying to @mstreng:

So the correct answer to binomial(Zmod(3)(1), 3) is "any integer modulo 3". Just returning Zmod(3)(0) is wrong. It would be ok to raise an error, I'd say ZeroDivisionError

Pari does this too.

There are of course some cases that we can still allow. Suppose the input is binomial(Zmod(n)(x), y).

Example with Pari:

? binomial(Mod(7,11),3)
%3 = Mod(2, 11)

videlec commented 9 years ago

comment:23

Hello,

I just discover this ticket. During a cleanup in sage.rings.arith (#17852) I took care of this case. I propose to close this one as duplicate. With the branch applied we got

sage: from sage.rings.arith import binomial
sage: R = Integers(6)
sage: binomial(R(5), R(2))
Traceback (most recent call last):
...
ZeroDivisionError: Inverse does not exist.
sage: R = Integers(21)
sage: binomial(R(5), R(2))
10
sage: binomial(R(5), R(2)).parent()
Ring of integers modulo 21

Vincent

mstreng commented 9 years ago

Description changed:

--- 
+++ 
@@ -20,11 +20,12 @@

 On input `binomial(x, y)`, what Sage should do instead is the following:
 * If the parent of y is Zmod(n) rather than ZZ, a `TypeError` should be raised.
-* If factorial(y) is zero or a zero-divisor in the parent of x, a `ZeroDivisionError` should be raised. This is automatic if one computes binomial(x, y) simply as
+* (This seems to be fixed by #17852) If factorial(y) is zero or a zero-divisor in the parent of x, a `ZeroDivisionError` should be raised. This is automatic if one computes binomial(x, y) simply as

x.parent()(prod([x-k for k in range(y)]) / factorial(y))

+   

 Apply:

mstreng commented 9 years ago

comment:24

Replying to @videlec:

sage: R = Integers(21) sage: binomial(R(5), R(2)) 10

This should be TypeError, because binomial(x,y) makes no sense when y is an element of R. It only makes sense when y is an integer. For example, binomial(5, 2) = 10, but binomial(5, 2+21) = 0.

So of the two points in the ticket description, the work in #17852 fixes the second one, but the first one is still open.

videlec commented 9 years ago

comment:25

Replying to @mstreng:

Replying to @videlec:

sage: R = Integers(21) sage: binomial(R(5), R(2)) 10

This should be TypeError, because binomial(x,y) makes no sense when y is an element of R. It only makes sense when y is an integer. For example, binomial(5, 2) = 10, but binomial(5, 2+21) = 0.

So of the two points in the ticket description, the work in #17852 fixes the second one, but the first one is still open.

Right!

videlec commented 9 years ago

comment:26

Hi,

Ticket #17852 is in pass to be positively reviewed. Let me summarize what will change when calling rings.arith.binomial(x,y):

y must be an integer (actually, I only asked that ZZ(y) does work and the first lines of code do y = ZZ(y))
the output type is always the type of x
if factorial(y) is not invertible a ZeroDivisionError is raised (I checked the behavior on many finite rings that I was able to think of)

Vincent

ea1d0bf8-c27a-4548-8cb7-de0b1d02441a commented 9 years ago

Stopgaps: todo

sagemath / sage

Binomial of integer (mod n) returns integer #12179