Project

General

Profile

Feature #898

« Previous | Next »

New function: cardinality of finite field?

Added by Anna Maria Bigatti about 8 years ago. Updated 4 months ago.

Status:
In Progress
Priority:
High
Assignee:
Anna Maria Bigatti
Category:
New Function
Target version:
CoCoALib-0.99880
Start date:
27 Jun 2016
Due date:
% Done:

20%

Estimated time:
Spent time:
1.45 h

Description

We currently have the function LogCardinality for a finite field.
Should we also have cardinality?
Should it work on other types?

Related issues

Related to CoCoALib - Feature #107: Recognizing finite fieldsClosed2012-03-19

Related to CoCoALib - Design #1232: IsPrime(0)Closed2018-10-29

History

#1 Updated by Anna Maria Bigatti about 8 years ago

#2 Updated by Anna Maria Bigatti about 8 years ago

JAA wrote in issue #107

JAA wonders whether ExtnDeg may not be a better name for LogCardinality. The name is clearer and can be applied more widely (e.g. to algebraic extensions over QQ).

#3 Updated by Anna Maria Bigatti about 8 years ago

  • Category set to New Function
  • Assignee set to Anna Maria Bigatti
  • Target version set to CoCoALib-0.99550 spring 2017

#4 Updated by John Abbott about 8 years ago

I'm not enthusiastic about a function for computing the cardinality.
  • As Anna recalled, there is already LogCardinality which probably ought to be just ExtnDeg (and which returns a machine integer);
  • A function to compute cardinality would have to return a BigInt.

Neither is a strong reason against.

What would the function be called? cardinality, FieldCardinality, FFCardinality?

The saving would be that one could write cardinality(Fq) instead of characteristic(Fq)^ExtnDeg(Fq), or perhaps just p^ExtnDeg(Fq) assuming p = characteristic(Fq).

You could argue that cardinality(Fq) is more readable than p^ExtnDeg(Fq)...

#5 Updated by Anna Maria Bigatti about 8 years ago

  • Subject changed from New function: cardinality of finite field to New function: cardinality of finite field?

John Abbott wrote:

I'm not enthusiastic about a function for computing the cardinality.
  • As Anna recalled, there is already LogCardinality which probably ought to be just ExtnDeg (and which returns a machine integer);
  • A function to compute cardinality would have to return a BigInt.

OK, I see the point, I was just wondering.... should we change name to LogCardinality and reject this issue?

#6 Updated by John Abbott about 8 years ago

  • Status changed from New to In Progress
  • % Done changed from 0 to 10

I think it makes most sense to change LogCardinality to ExtnDeg (any other candidate names?), and then to reject this issue. However, changing a name is not backward compatible :-(

If at a later stage, we really do want a cardinality fn for finite fields, it would be a trivial one-liner. Anyway, at the moment it is not clear to me what such a fn should be called: cardinality seems to be a too general to me.

PS: please don't delete this issue; I would like there to be a record that we discussed it, and why we rejected it.

#7 Updated by Anna Maria Bigatti about 8 years ago

John Abbott wrote:

I think it makes most sense to change LogCardinality to ExtnDeg (any other candidate names?), and then to reject this issue. However, changing a name is not backward compatible :-(

How about ExtensionDeg?

#8 Updated by John Abbott about 8 years ago

  • % Done changed from 10 to 20

ExtensionDeg is certainly clearer than ExtnDeg. Right now I cannot think of any good reason to push for succinctness, and anyway if you really want succinctness then you can always do const int d = ExtensionDeg(K); and use d in subsequent formulas.

#9 Updated by John Abbott almost 8 years ago

  • Target version changed from CoCoALib-0.99550 spring 2017 to CoCoALib-0.99560

The name ExtensionDeg is very tempting, and "feels quite mathematical". However, I am uncertain what its interface should be.

One suggestion is that it takes just one arg, and computes its (algebraic) extension degree over the corresponding prime field. Another possibility is for there to be 2 args (namely, a larger field and a smaller field -- in which order?) and the fn computes the extension of the larger field over the smaller one. This 2 arg version seems potentially more complicated to implement, and JAA is not sure how useful it would be over the simpler 1 arg version: should it work for inputs such as QQ(x)[y]/ideal(y^2-2) and QQ(x)?
Maybe it is just a call to IsZeroDim, IsMaximal and multiplicity???

#10 Updated by John Abbott over 6 years ago

  • Target version changed from CoCoALib-0.99560 to CoCoALib-0.99600

#11 Updated by Anna Maria Bigatti almost 6 years ago

  • Target version changed from CoCoALib-0.99600 to CoCoALib-0.99650 November 2019

#12 Updated by John Abbott over 5 years ago

  • Priority changed from Normal to High

I have just noticed that LogCardinality is not implemented as I expected: it returns 0 when applied to a poly ring QQ[x,y,z]. I would have expected an error.

Maybe we should fix the semantics (see comment 9 -- probably use the 1 arg version), fix the implementation, and change the name (and manuals!)

Perhaps there should be a fn IsAlgExtn too, so that we know when we can apply "extension degree".

#13 Updated by John Abbott over 5 years ago

#14 Updated by John Abbott almost 5 years ago

  • Target version changed from CoCoALib-0.99650 November 2019 to CoCoALib-0.99700

#15 Updated by John Abbott over 4 years ago

  • Target version changed from CoCoALib-0.99700 to CoCoALib-0.99800

#16 Updated by John Abbott over 3 years ago

Since we intend restricting its use to finite fields maybe the fn could be called FieldSize; error if arg is not a finite field.

We could also write ExtensionDeg with just 1 arg which must either be a finite field or a finite alg extn of QQ.

#17 Updated by John Abbott over 3 years ago

I have now changed the default defn of myLogCardinality so that it throws an exception; the finite fields overwrite this default defn.

#18 Updated by John Abbott over 2 years ago

  • Target version changed from CoCoALib-0.99800 to CoCoALib-0.99850

#19 Updated by John Abbott 4 months ago

  • Target version changed from CoCoALib-0.99850 to CoCoALib-0.99880

Also available in: Atom PDF