euler_phi broken #52
Comments
|
I suppose we can change the Nemo and Oscar definitions to return 0 for negative values. But the rest just look like bugs to me. |
|
On Fri, Nov 15, 2019 at 01:42:51PM -0800, wbhart wrote:
The following works fine in Nemo, but is broken in Hecke:
Even better... I actualyl did not realize this, but
eulerphi (one word) works, possibly as intended,
euler_phi (underscore) should be removed
and the other ones possibly be removed as well if we're getting them
from Nemo.
But there is also the version giving the factored form.
```
julia> typeof(euler_phi(0))
I'd say this is correct to give an error - we can discuss which error.
ERROR: AssertionError: N > 0
Stacktrace:
[1] factor(::Nemo.fmpz) at /home/wbhart/.julia/packages/Hecke/HqBPo/src/Misc/Integer.jl:815
[2] factor(::Int64) at /home/wbhart/.julia/packages/Hecke/HqBPo/src/Misc/Integer.jl:719
[3] euler_phi(::Int64) at /home/wbhart/.julia/packages/Hecke/HqBPo/src/analytic.jl:247
[4] top-level scope at none:0
julia> typeof(euler_phi(1))
Int64
julia> typeof(euler_phi(2))
Nemo.fmpz
```
which of the 2 is correct? In Hecke, eulerphi(a::T) T <: Integer returns
type T. I don't know (any more) if this is good/bad/?
…
--
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
#52
|
That's the Nemo version.
This is an assertion, not an error. And it's not an assertion in euler_phi but in the factoring code. That's obviously not supposed to happen.
I don't mind. Obviously it is possible to define euler_phi(::T) -> T if you want. Unfortunately it is not implemented that way in Nemo. I'd use the Hecke version for Int if it were not broken. But of course I'd stick it in Nemo, along with the fmpz version. What's not good is the type instability Hecke exhibits. I've just removed it from my local version of Hecke and use the Nemo version instead. Once you guys decide what you prefer and fix Hecke, the Oscar tests can be made to pass.
|
|
On Mon, Nov 18, 2019 at 02:24:41AM -0800, wbhart wrote:
> On Fri, Nov 15, 2019 at 01:42:51PM -0800, wbhart wrote: The following works fine in Nemo, but is broken in Hecke:
> Even better... I actualyl did not realize this, but eulerphi (one word) works, possibly as intended,
That's the Nemo version.
> euler_phi (underscore) should be removed and the other ones possibly be removed as well if we're getting them from Nemo. But there is also the version giving the factored form.
> ``` julia> typeof(euler_phi(0))
> I'd say this is correct to give an error - we can discuss which error.
This is an assertion, not an error. And it's not an assertion in euler_phi but in the factoring code. That's obviously not supposed to happen.
> ERROR: AssertionError: N > 0 Stacktrace: [1] factor(::Nemo.fmpz) at /home/wbhart/.julia/packages/Hecke/HqBPo/src/Misc/Integer.jl:815 [2] factor(::Int64) at /home/wbhart/.julia/packages/Hecke/HqBPo/src/Misc/Integer.jl:719 [3] euler_phi(::Int64) at /home/wbhart/.julia/packages/Hecke/HqBPo/src/analytic.jl:247 [4] top-level scope at none:0 julia> typeof(euler_phi(1)) Int64 julia> typeof(euler_phi(2)) Nemo.fmpz ```
> which of the 2 is correct? In Hecke, eulerphi(a::T) T <: Integer returns type T. I don't know (any more) if this is good/bad/?
I don't mind. Obviously it is possible to define euler_phi(::T) -> T if you want. Unfortunately it is not implemented that way in Nemo. I'd use the Hecke version for Int if it were not broken. But of course I'd stick it in Nemo, along with the fmpz version.
What's not good is the type instability Hecke exhibits.
I've just removed it from my local version of Hecke and use the Nemo version instead. Once you guys decide what you prefer and fix Hecke, the Oscar tests can be made to pass.
> […](#)
> -- You are receiving this because you are subscribed to this thread. Reply to this email directly or view it on GitHub: #52
euler_phi in Hecke should not be there.
eulerphi needs to be renamed and restricted to the functions not
provided by Nemo
Then we can see if it can be transferred...
…
--
You are receiving this because you commented.
Reply to this email directly or view it on GitHub:
#52 (comment)
|
|
Unfortunately, there is no way of being consistent with Julia without making functions that take an Int return an Int. Julia does this for factorial and binomial, so we are stuck with it. At present in Oscar I have it so that you have to do Oscar.binomial or Oscar.factorial to get the Nemo version. But this is inconsistent, as @rfourquet has pointed out, as some of our other similar functions take an Int and return an fmpz, and we export those. There are only two consistent approaches possible (since you can't add functions to Base):
I'm now leaning towards 2, but if you prefer 1, I can live with it. Just let me know what you decide. |
|
On Mon, Nov 18, 2019 at 04:16:57AM -0800, wbhart wrote:
Unfortunately, there is no way of being consistent with Julia without making functions that take an Int return an Int. Julia does this for factorial and binomial, so we are stuck with it.
At present in Oscar I have it so that you have to do Oscar.binomial or Oscar.factorial to get the Nemo version. But this is inconsistent, as @rfourquet has pointed out, as some of our other similar functions take an Int and return an fmpz, and we export those.
There are only two consistent approaches possible (since you can't add functions to Base):
1) Don't export any of our combinatorial/number_theoretic functions, so that we can define versions that take an Int and return an fmpz.
2) Export our functions, but only define them for Int->Int (if at all) and fmpz->fmpz.
I'm now leaning towards 2, but if you prefer 1, I can live with it. Just let me know what you decide.
I vote for 2
…
--
You are receiving this because you commented.
Reply to this email directly or view it on GitHub:
#52 (comment)
|
|
Since we are agreed. I will go ahead and implement this in Nemo and Oscar (@rfourquet also prefers this, if I understand correctly). I'm not going to implement any Int->Int versions for now. People can add them later if they are needed. (Or they can be moved over from Hecke, if they exist and work correctly.) |
|
I indeed also prefer 2, and I can help implement this. If we want to expose the versions |
|
On Mon, Nov 18, 2019 at 05:19:56AM -0800, Rafael Fourquet wrote:
I indeed also prefer 2, and I can help implement this. If we want to
expose the versions `Int -> fmpz` (for performance reasons, if we find
it matters, i.e. to not have to call `factorial(ZZ(100))`, which
itself converts `ZZ(100)` back to `Int` before `ccall`ing into Flint),
we migth (eventually) add a method taking an output type, e.g.
`factorial(ZZ, 100)`.
While I agree, I cannot for the immediate future see that we will be
able to write all functions in a version with output type.
Some yes: floor, ceil, round, ...
all: no, too much work
…
--
You are receiving this because you commented.
Reply to this email directly or view it on GitHub:
#52 (comment)
|
|
On Fri, Nov 15, 2019 at 01:46:19PM -0800, wbhart wrote:
I suppose we can change the Nemo and Oscar definitions to return 0 for negative values. But the next two just look like bugs to me.
Why 0 for negative values? phi(x) = phi(-x) would be my guess as Z/x =
Z/-x and thus counting units gives the same results?
…
--
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
#52 (comment)
|
FWIW, it's what PARI does. |
|
And of course Sage defines it to be zero. It just depends on which definition you use. I can change the Nemo definition if you like. Just let me know if this is what you want. |
|
On Mon, Nov 18, 2019 at 08:55:35AM -0800, wbhart wrote:
And of course Sage defines it to be zero. It just depends on which definition you use.
I can change the Nemo definition if you like. Just let me know if this is what you want.
I think mathematically, there are two main possibilities:
- error for n < 1
- phi(n) = phi(-n) and error for 0 (or 2 as Z/0Z = Z has units +-1
...)
setting it to zero outside the area where it is defined is strange.
Unless Sage also sets gcd(3, -5) to be -1, then there are "no" coprime
positive integers...
But mathematically, either
phi(n) = |Z/nZ^*|, possibly excluding 0
or
phi(n) is only defined for positive n....
… --
You are receiving this because you commented.
Reply to this email directly or view it on GitHub:
#52 (comment)
|
|
It's often defined as the number of integers in 1 <= k <= n such that gcd(k, x) = 1. That is well defined for all integers and is zero for n <= 0. The fact that it happens to equal |Z/nZ^*| for positive n is a bonus. Clearly, it depends on the definition you take. I understand that you have a different definition than the one we chose. |
|
Anyway, I will change the definition, as your definition also satisfies: phi(n) = sum_{d|n} mu(n) (n/d) where mu is the Moebius function. But we should make all our number theoretic functions defined on zero (where possible) and negative n if we do so for this one. |
|
On Tue, Nov 19, 2019 at 02:31:37AM -0800, wbhart wrote:
Anyway, I will change the definition, as your definition also satisfies:
phi(n) = sum_{d|n} mu(n) (n/d)
where mu is the Moebius function. But we should make all our number
theoretic functions defined on zero (where possible) and negative n if
we do so for this one.
Depends on your view...
The reason I want this is not because its number theoretic, thats a
bonus, but I also want
euler_phi(nmod_poly) and euler_phi(ideal with finite quotient)
some of other functions also make sense here (lambda e.g.) but I am not
sure about the sigmas
…
--
You are receiving this because you commented.
Reply to this email directly or view it on GitHub:
#52 (comment)
|
|
It's just that these functions have a meaning in classical number theory (where they were first defined), which depends on prime numbers only being positive. I'm not sure they can be used to count things correctly if they don't have the classical definition. We might need two definitions of all these functions, one for N and the other for Z. Currently Nemo typically takes the definitions for N. |
|
On Tue, Nov 19, 2019 at 02:45:51AM -0800, wbhart wrote:
It's just that these functions have a meaning in classical number
theory (where they were first defined), which depends on prime numbers
only being positive. I'm not sure they can be used to count things
correctly if they don't have the classical definition.
The classical definitions were always only for pos (non negative)
Anyone using this outside this range is already using their
generalisation (and their risk)..
We might need two definitions of all these functions, one for N and
the other for Z. Currently Nemo typically takes the definitions for N.
As long as there is no conflict...
the definition for N makes negative arguments illegal
…
--
You are receiving this because you commented.
Reply to this email directly or view it on GitHub:
#52 (comment)
|
|
I will check, but I am not sure if that is true. I think there are results involving Hecke L-series that rely on the functions having value 0 at negative integers, otherwise you get double counting. Similarly for the theory of binary quadratic forms, I think you count over all integers and rely on the function taking value zero at negative values. But as I say, I need to look into this. If standard theorems don't work with the new definitions then we'll just have to ask people to define their own functions if they want the non-standard definitions. But let me check into this before getting too concerned. As long as everything is ok, I'm happy to use your definitions. Obviously it works for the Pari/GP guys. |
|
So it looks to me like the most important theorem involving multiplicative arithmetic functions is that they form a group under Dirichlet convolution. There are also various relations among the functions like f(n) = 1, f(n) =1, sigma(n), tau(n), phi(n), mu(n), etc. under Dirichlet convolution, and these better continue to hold. The formula is given by (f*g)(n) = sum_{d|n} f(d) g(n/d) where it is easy to check that this only makes sense if you only consider positive divisors d. However, note that for negative n, both sides of the equation have functions defined at negative n. The identity for the Dirichlet convolution is defined by e(1) = 1 and e(n) = 0 for all n > 1. This doesn't shed much light on the value of e at negative n. The real problem I have with defining phi(-n) = phi(n) is the product formula for phi(n): phi(n) = n prod_{p|n} (1-1/p) where the product is over all primes dividing n. You can see that this leads to negative, not positive values of phi(n) at negative n, and I think phi(0) = 0 with this definition. |
|
Ok, after looking into this, phi(0) is either left undefined or given the value 0, 1 or 2 depending on your definition of phi. I can't find any mathematical reference that defines if for negative n. I'd like to see one before doing that. As I see it, the function has the following definition everywhere: "phi(n) is the number of integers in the range 1 <= k <= n such that gcd(k, n) = 1". This makes phi(n) = 0 for n < 1 (though someone claimed that by convention phi(0) = 1, and backed it up with some reference to a theorem about the length of Farey sequences, which I find dubious). For positive n it is true that phi(n) = |(Z/nZ)*|. But this is not a convenient definition, otherwise how do I define all the other arithmetic functions? Do they have definitions in terms of (Z/nZ)*? I really don't think it makes any sense to use the standard definitions for all other arithmetic functions, but use the definition in terms of (Z/nZ)* for this one function phi. Obviously, extending the function to the negative integers can be done in more than one way, but is only compatible with theorems for phi(n) if you choose the right definition. That's a very good reason to not define it there. If people want it to be defined there for a certain application, let them define their own version. E.g. Hecke could not import the Nemo definition, define its own version and not export the definition. In my opinion, we can't just keep changing the definition of our functions based on the need to have it defined this way or that way depending on the application. |
|
On Tue, Nov 19, 2019 at 06:56:46AM -0800, wbhart wrote:
So it looks to me like the most important theorem involving multiplicative arithmetic functions is that they form a group under Dirichlet convolution. There are also various relations among the functions like f(n) = 1, f(n) =1, sigma(n), tau(n), phi(n), the von Mangolt function, mu(n), etc. under Dirichlet convolution, and these better continue to hold.
The formula is given by
(f*g)(n) = sum_{d|n} f(d) g(n/d)
where it is easy to check that this only makes sense if you only consider positive divisors d. However, note that for negative n, both sides of the equation have functions defined at negative n.
The identity for the Dirichlet convolution is defined by e(1) = 1 and e(n) = 0 for all n > 1. This doesn't shed much light on the value of e at negative n.
The real problem I have with defining phi(-n) = phi(n) is the product formula for phi(n):
phi(n) = n prod_{p|n} (1-1/p) where the product is over all primes dividing n.
You can see that this leads to negative, not positive values of phi(n) at negative n, and I think phi(0) = 0 with this definition.
Only if you believe the identities are valid (or should be valid) for
negative n
"Sensible" people are using phi only for n>0, not even 0, as this is the
"traditional" domain for phi.
I am proposing a more "mathematical" definition as |Z/nZ^*| which agrees
with the tradition in the traditional domain, thus causing no problems
there, while opening the door to more general cases.
In the end, it does not matter, and we will encounter this in many
situations. Sometimes, clearly the traditional definition will turn out
to be "wrong", sometimes the new one is stupid...
… --
You are receiving this because you commented.
Reply to this email directly or view it on GitHub:
#52 (comment)
|
|
On Tue, Nov 19, 2019 at 07:52:54AM -0800, wbhart wrote:
Ok, after looking into this, phi(0) is either left undefined or given
the value 0, 1 or 2 depending on your definition of phi.
I can't find any mathematical reference that defines if for negative
n. I'd like to see one before doing that. As I see it, the function
has the following definition everywhere:
"phi(n) is the number of integers in the range 1 <= k <= n such that
gcd(k, n) = 1". This makes phi(n) = 0 for n < 1 (though someone
claimed that by convention phi(0) = 1, and backed it up with some
reference to a theorem about the length of Farey sequences, which I
find dubious).
I would never use this definition as this captures absolutely nothing.
To show, from there, that this is multiplicative is a nightmare, as in
step 1: link it to Z/nZ^*
step 2: done
For positive n it is true that phi(n) = |(Z/nZ)*|.
But this is not a convenient definition, otherwise how do I define all
the other arithmetic functions? Do they have definitions in terms of
(Z/nZ)*?
All the others? Most of the artithmetic functions are defined in some
context, depending on the problem you want to investigate. The problems
have changed, so have the "convenient" definition.
Some (at least one) can be phrased this way:
lambda is the exponent of Z/nZ^*, thus has such a definition
I don't think there is a elementary, natural definition for Carmichael
lambda...
Lengendre as well:
legendre(a,b) = 1 if order a in Z/bZ^* is even, -1 otherwise
if this is more or less natural than the other, I don't know.
What is clear though is that the "very classical" definition is a
cul-de-sac: it cannot be extended in any useful way to more situations.
I really don't think it makes any sense to use the standard
definitions for all other arithmetic functions, but use the definition
in terms of (Z/nZ)* for this one function phi.
Obviously, extending the function to the negative integers can be done
in more than one way, but is only compatible with theorems for phi(n)
if you choose the right definition. That's a very good reason to not
define it there.
There are no theorems for phi(n) involving negative n, so I don't see
that argument, but at the end, we'll see.
I can see more complaints about the lack of phi(-2) then I forsee about
the "wrong" definition.
If people want it to be defined there for a certain application, let
them define their own version. E.g. Hecke could not import the Nemo
definition, define its own version and not export the definition.
In my opinion, we can't just keep changing the definition of our
functions based on the need to have it defined this way or that way
depending on the application.
We do this all the time. The key is though to try to keep is consistent.
Also: extending the definition is less harmful than changing old values:
defining phi(4) = 5 would be deadly
Defining phi(-4) = 5 would be stupid, but not tragic.
But be my guest, produce errors for phi(n) n<1.
…
--
You are receiving this because you commented.
Reply to this email directly or view it on GitHub:
#52 (comment)
|
The following works fine in Nemo, but is broken in Hecke:
The text was updated successfully, but these errors were encountered: