euler_phi broken about hecke.jl HOT 23 CLOSED

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.

from hecke.jl.

from hecke.jl.

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.

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

from hecke.jl.

from hecke.jl.

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.

from hecke.jl.

from hecke.jl.

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.)

from hecke.jl.

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 ccalling into Flint), we migth (eventually) add a method taking an output type, e.g. factorial(ZZ, 100).

from hecke.jl.

from hecke.jl.

from hecke.jl.

phi(x) = phi(-x) would be my guess

FWIW, it's what PARI does.

from hecke.jl.

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.

from hecke.jl.

from hecke.jl.

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.

from hecke.jl.

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.

from hecke.jl.

from hecke.jl.

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.

from hecke.jl.

from hecke.jl.

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.

from hecke.jl.

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.

from hecke.jl.

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.

from hecke.jl.

from hecke.jl.

from hecke.jl.