#12179: Binomial of integer (mod n) returns integer
----------------------------------------------------+-----------------------
Reporter: scotts | Owner:
AlexGhitza
Type: defect | Status:
needs_work
Priority: major | Milestone: sage-5.7
Component: basic arithmetic | Resolution:
Keywords: binomial coefficient modulo sd35 | Work issues:
Report Upstream: N/A | Reviewers: Colton
Pauderis, Johan Bosman, Marco Streng
Authors: Sam Scott | Merged in:
Dependencies: #11417 | Stopgaps:
----------------------------------------------------+-----------------------
Changes (by mstreng):
* status: needs_review => needs_work
* work_issues: rebase on top of #11417, reST formatting issue, improve
efficiency =>
Old description:
> {{{
> sage: R = Integers(6)
> sage: binomial(R(5), R(2))
> 10
> sage: binomial(R(5), R(2)).parent()
> Integer Ring
> }}}
>
> Wouldn't we expect the answer to be 4 and an element of R?
>
> The offending code is in the method binomial of
> [http://trac.sagemath.org/sage_trac/browser/sage/rings/arith.py
> 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.
New description:
{{{
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 `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))
}}}
--
Comment:
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
`ZeroDivisionError`s 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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12179#comment:13>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
