GuessStrategy -- an option for the function fpt to specify the criterion used for selecting numbers to check

In the computation of the $F$-pure threshold of a polynomial $f$, in nontrivial cases and when no special algorithm is used, the function fpt uses frobeniusNu to find a closed interval [$A$, $B$] that contains the $F$-pure threshold of $f$. The subroutine guessFPT is then called, to first check whether one of the endpoints $B$ or $A$ is the $F$-pure threshold, and then to select rational numbers in the interval, and check how they are positioned in relation to the $F$-pure threshold, using the function compareFPT. The option GuessStrategy controls how this selection of numbers is done.

We start by describing what happens when GuessStrategy is set to null, its default value. First, a list of several rational numbers in the interval ($A$, $B$) is created and, using the function decomposeFraction from the TestIdeals package, each number $t$ in that list is written in the form $t = a$ /($p^b$ ($p^c$ - 1)), where $p$ is the characteristic of the ambient ring. That list of candidates is then sorted based on

1. Increasing "computational cost" $w_aa + w_bb + w_cc$, for certain weights $w_a$, $w_b$, and $w_c$,

and then refined by

2. Increasing distance from the midpoint of the interval ($A$, $B$).

Once this sorting is done, the first number in the list is selected, compareFPT is called, and the result of that comparison is used to trim the list of candidates and narrow down the interval ($A$, $B$). This process is iterated as many times as requested by the user, via the option Attempts. If the supply of candidates runs low, more are produced.

The default weights currently used in Criterion 1 are $w_a =$ 0, $w_b =$ 1, and $w_c =$ 1.5. With these choices, we believe Criterion 1 is likely to prioritize numbers for which the computation of compareFPT is most efficient. Criterion 2, on the other hand, aims at partitioning the interval as evenly as possible.

The option GuessStrategy allows the user to choose his or her own weights for Criterion 1. In that case, the list is sorted based on Criterion 1 with the user's weights, and then Criterion 1 with default weights and Criterion 2, respectively, are used as tie breakers. For instance, if the user suspects that the (minimal) denominator of the $F$-pure threshold is prime to the characteristic $p$, then weights $w_a =$ 0, $w_b =$ 1, and $w_c =$ 0 might be a reasonable choice to try to find that $F$-pure threshold with fewer trials.

i1 : R = ZZ/11[x,y];

i2 : f = 6*x^6*y^7 + 8*x^4*y^7 + 8*x^3*y^7 + 6*x^6*y^3 + 5*x^5*y^4 + 4*x^3*y^6 +4*x^3*y^5

         6 7     4 7     3 7     6 3     5 4     3 6     3 5
o2 = - 5x y  - 3x y  - 3x y  - 5x y  + 5x y  + 4x y  + 4x y

o2 : R

i3 : fpt(f, Attempts => 5, DepthOfSearch => 3)

       29   317
o3 = {---, ----}
      122  1331

o3 : List

i4 : fpt(f, Attempts => 5, DepthOfSearch => 3, GuessStrategy => {0, 1, 0})

      5
o4 = --
     21

o4 : QQ

The user may also pass his or her own "cost" functions, that may take as input any of the following: the candidate rational number $t$, the pair ($p$, $t$), where $p$ is the characteristic of the ambient ring, or ($p$, $a$, $b$, $c$), where the integers $a$, $b$, and $c$ are as described above. The list of candidates is then sorted first by increasing values of that function, and Criteria 1 and 2, respectively, are used as tie breakers. For instance, if the user suspects the $F$-pure threshold has a small denominator, then passing the function denominator may help find the answer in fewer trials.

i5 : R = ZZ/5[x,y];

i6 : f = x^3*y^11*(x + y)^8*(x^2 + y^3)^8;

i7 : fpt(f, DepthOfSearch => 3, Attempts => 7)

       5   4
o7 = {--, --}
      96  75

o7 : List

i8 : fpt(f, DepthOfSearch => 3, Attempts => 4, GuessStrategy => denominator)

      1
o8 = --
     19

o8 : QQ