ZZRingElem vs Int in polyhedral geometry (and beyond)

[micjoswig]

Let's start with an example:

julia> @show f_vector(cube(3));
f_vector(cube(3)) = ZZRingElem[8, 12, 6]

The f-vector counts the number of faces per dimension; so a 3-dimensional cube has 8 vertices, 12 edges and 6 facets.

My question is if ZZRingElem is the correct type here, and I am inviting your opinions. Some of my reasoning is mainly philosophical, but there are also technical considerations.

• in mathematical terms, the integers here occur in their incarnation as (finite) cardinals; there is no natural ring structure (despite the fact that sums of cardinals and products exist)
• long integers (which implement ZZRingElem) are slow
• in arguments of functions indirectly related we use Int

For example, the second parameter (5) is an Int:

julia> rand_subpolytope(cube(3), 5)
Polyhedron in ambient dimension 3

and I don't think there is a reasonable way to change that to ZZRingElem.

• In polymake we had started out with 32 bit Ints a long time ago, and then it became a problem. With Int64 there is some room; more importantly, it can be expected that future versions of Julia will ultimately move to 128 bit Ints. By sticking to standard data types (like Int) we can benefit from such upgrades, without any effort.

@lkastner @tbrysiewicz @thofma @fingolfin

[wdecker]

We are having a similar discussion with regard to invariants in the commutative algebra part (dimension, hilbert function, degree, ...)

[thofma]

We do not have any rules on whether a function should return an Int or a ZZRingElem. What is used has been up to the person implementing the function.

• The type Int is used where it matters for speed. For example nrows(M) of a matrix M or degree(f) for a univariate polynomial return Int. There is also no danger of wrong results, since it is technically impossible to construct a (dense) matrix with more than 2^64 rows.

• The type ZZRingElem should be used, when the result might overflow an Int. For example, this the case for order(G) of a group (the integer here occurs as a finite cardinal, so I don't see this as an argument for using Int):

julia> typeof(order(symmetric_group(30)))
ZZRingElem

• Regarding performance, it depends of course on the application. Is there a practical application, where the computation with f-vector components is more costly than the computation of the f-vector itself?

• There are lots of functions of the form f(x::Int) = do something and f(x::ZZRingElem) = f(Int(x)).

P.S.: I find the following behaviour not user-friendly:

julia> Qx, x = PolynomialRing(QQ, 20);

julia> I = ideal(Qx, [x[i]^10 for i in 1:20]);

julia> degree(I)
ERROR: InexactError: convert(Int64, 100000000000000000000)
Stacktrace:
 [1] Int64(a::ZZRingElem)

Imagine I spent a few weeks on my server with a computation and in the end it failed, because Oscar wanted to convert something to Int, which it should not.

[micjoswig]

I like the examples with the group order and the degree of an ideal. I agree that my previous comment on cardinals was not a good argument, and I also agree that long integers are a good idea for these. And probably it is not a good idea to have two versions of the same (i.e., long integers for such cases and another version of long integers for actual algebaric manipulations).

Somehow, f-vectors are different though. For an arbitrary polytope I don't see a way to produce the f-vector without actually counting the faces. That is, the faces need to be constructed before you can have the f-vector. In this sense, the same reasoning applies as for rows and columns of matrices.

In this way, I would try to argue again for ordinals (the faces are produced consecutively). A lot of the underlying polymake functions rely on indices for vertices, facets, edges, ... So there is currently no technical way to have more than 2^64 of those.

There is one scenario, in which long integers for f-vectors do make sense. This occurs for translating f-vectors into h-vectors and conversely, or for explicitly computing the upper bound in McMullen's upper bound theorem. But that does not require the standard f_vector function to return long integer values.

[thofma]

If there is no possibility of a (silently) wrong result, I see no reason for f_vector not to return a Vector{Int}.

[fieker]

The problem is the inteaction with the rest: if I do vcat(...) to do linear algebra later, how difficult is this to convert? What functionality will be supported for Vector Int? What are we allowed to provide for this type?

[JohnAAbbott]

If there are situations where it is convenient to have an f-vector with ZZRingElem entries (regardless of overflow considerations) then it might be reasonable to allow the caller to specify what type of answer to: e.g. two functions with similar names, one which returns Vector{Int} and one which returns Vector{ZZRingElem}.
We could also use an optional parameter to choose between return types, but that would lead to "type instability" (not sure if that would really be a problem in this case).