AngouriMath

Navigation

Home Quick start Wiki Almanac Research What's new Try Use Angouri.org GitHub Report a bug Donate Contacts

AngouriMath.Functions

← Back to list of namespaces

Classes within the AngouriMath.Functions namespace

• BaseConversion

• BinomialIdentities

  Summary

  The binomial sums of chapter 8 of Sullivan and Mackey's An Introduction to Proofs that are not the binomial theorem itself, in closed form: a polynomial in the index
  beside the coefficient (Prop 8.4.4, sum(k binomial(n, k), k, 0, n) is
  n 2^(n - 1)), Vandermonde's convolution (Prob 8.9.16,
  sum(binomial(a, i) binomial(b, k - i), i, 0, k) is binomial(a + b, k)) and
  its square case (Prob 8.9.34, sum(binomial(n, k)^2, k, 0, n) is
  binomial(2n, n)), the summation identity (Thm 8.4.6,
  sum(binomial(i, k), i, 0, n) is binomial(n + 1, k + 1)), the sums over
  the even or the odd indices (Ex 8.3.11, each 2^(n - 1) for n >= 1), the
  trinomial revision summed (Prob 8.9.15, sum(binomial(n, i) binomial(n - i, k - i), i, 0, k) is 2^k binomial(n, k), and §8.4.5's sum(binomial(n, i) binomial(i, k), i, k, n),
  2^(n - k) binomial(n, k)), the parallel summation (Prob 8.9.19,
  sum(binomial(r + i, i), i, 0, n) is binomial(r + n + 1, n)) and Vandermonde along
  the upper indices (Prob 8.9.18, sum(binomial(j, a) binomial(m - j, b), j, 0, m) is
  binomial(m + 1, a + b + 1)).
  

  Remarks

  A polynomial beside the coefficient is read in the falling factorial basis,
  k^m = sum_j S(m, j) k (k - 1) ... (k - j + 1) with the Stirling numbers of the second
  kind, because k (k - 1) ... (k - j + 1) binomial(n, k) is
  n (n - 1) ... (n - j + 1) binomial(n - j, k - j) -- the chairperson identity
  applied j times -- so sum_k k^(j falling) binomial(n, k) x^k y^(n - k) is
  n^(j falling) x^j (x + y)^(n - j) by the binomial theorem on what is left. Exact for
  every whole n >= 0 and every x, y; the empty range below zero is
  the piecewise PolynomialSummation attaches.
  Vandermonde holds as an identity in a and b for whole a, b >= 0 and a whole k >= 0, the terms outside 0 <= i <= min(a, k) being zero, so the
  range may be written to k, to a, or to b where the second coefficient
  is binomial(b, k - i). The square is the case a = b = k = n with
  binomial(n, k) = binomial(n, n - k). The summation identity is Pascal's rule
  telescoped. Part of #1409.
  

• BinomialSum

  Summary

  A summation over k from 0 to N of the binomial coefficient
  N! / (k! (N - k)!) times a power or a trigonometric weight, in closed form:
  sum(N! / (k! (N - k)!) x^k, k, 0, N) is (1 + x)^N, and
  sum(N! / (k! (N - k)!) cos(k t), k, 0, N) is (2 cos(t/2))^N cos(N t / 2).
  

  Remarks

  The binomial theorem read backwards. With weights x^k y^(N-k) the sum is
  (x + y)^N, either power optional. With cos(k t) it is the real part of
  (1 + e^(i t))^N, and 1 + e^(i t) = 2 cos(t/2) e^(i t/2) exactly, so the sum is
  (2 cos(t/2))^N cos(N t/2); with sin(k t) the same with the sine. Both hold for
  every complex t, since cos z = (e^(iz) + e^(-iz)) / 2 is the definition
  and the two conjugate sums add: no assumption on t is owed.
  The one condition is the range: for N below zero the summation is empty and this
  library answers an empty range with 0, while the formula does not, so a symbolic
  N gets the same piecewise PolynomialSummation attaches. Recognised
  structurally, on the factors of the simplified summand: the three factorials with
  N the upper bound as written, at most one power in k, at most one in
  N - k, at most one cosine or sine of k times something free of it, and
  nothing else that mentions k. A trigonometric weight beside a power is declined:
  the closed form then needs the modulus and argument of y + x e^(i t), which is
  not a simplification. Question II.3 of
  #1212.
  

• BivariateHenselFactorization

  Summary

  Factorisation in two variables by Hensel lifting along an evaluation
  homomorphism: factor the polynomial at a point, then lift that factorisation back
  one power of the auxiliary variable at a time.
  

  Remarks

  KroneckerFactorization reaches the same answers by a different route and
  leaves a gap this fills. Its one-variable image has degree Π (d_i + 1) - 1, and —
  worse than the size — the image over-factors: x^7 - y^7 maps to
  t^7 (1 - t^49), whose factors are cyclotomic, so the recombination is exponential
  in a count the substitution itself inflated. An evaluation image does not inflate
  anything: x^7 - y^7 at y = 1 is x^7 - 1, which has the two factors
  the answer has.
  The lift. Write g(x, y) = f(x, y + a) so that the point is the origin.
  g(x, 0) factors over the integers as u_1 · … · u_r, and a factorisation
  modulo y^k is pushed to y^(k+1) by solving α·v + β·u = e for the
  error e — which the Bezout pair of u and v answers immediately,
  since a square-free image makes them coprime. Reducing α below the degree of
  u and pushing the quotient into β keeps each side at the degree it started
  at. Lifted as far as the degree of g in y, a true factor is reached
  exactly rather than approximately, because it has no higher power to hide in.
  What is restricted, and why it is the honest restriction rather than a convenient
  one. The leading coefficient in the main variable must be constant. Where it is a
  polynomial in y, the lifted factors' leading coefficients have to be *known in
  advance* to keep them polynomials rather than power series — Wang's leading-coefficient
  problem — and the usual answer is to factor that coefficient and distribute it, which is
  a second algorithm on top of this one. Declining is a refusal, and refusing is something
  this layer already does.
  Nothing here is trusted. Every candidate is checked by exact division of the
  original, so a mistake anywhere above — a bad point, a lift that drifted, a recombination
  that is not a factor — costs a refusal and cannot cost a wrong answer.
  

• DivergentSeries

  Summary

  A summation to +oo whose terms do not tend to zero, which therefore has no finite
  value: sum(2^k, k, 0, +oo) and sum(n^n, n, 1, +oo) are +oo.
  

  Remarks

  The nth-term test: if the terms do not tend to zero the series diverges. That alone
  says a series has no sum; it does not say what to answer instead. What settles the answer is
  the sign of the limit — where the terms tend to a positive L, they are
  eventually all above L / 2, so the partial sums pass every bound and the value is
  +oo; a negative limit gives -oo the same way. The finitely many terms before
  that point are finite and cannot change it.
  A limit of zero is declined, and that is the whole difficulty of the test. It is
  exactly the case the nth-term test says nothing about: sum(1/k) diverges and
  sum(1/k^2) converges, and their terms both tend to 0. Answering either from this
  reader would be a guess. So would a limit that does not exist — sum((-1)^k) has no
  value rather than an infinite one — and that is left as written too, since telling "the
  limit does not exist" apart from "the limit was not computed" is not something to infer
  from a failed computation.
  The summand must have no pole in the index, and this is checked before the limit is
  asked for. A single undefined term makes the whole sum undefined, not infinite:
  sum(k / (k - 5), k, 0, +oo) has terms tending to 1, and answering +oo would
  be wrong because the term at k = 5 does not exist. Rather than hunt for poles, the
  index is allowed to occur only where none can arise — under +, -, *,
  and powers of the three shapes HasNoPoleInTheIndex(AngouriMath.Entity,AngouriMath.Entity.Variable,AngouriMath.Entity.Number.Integer) lists. Division by
  anything containing the index, a factorial of it, a logarithm of it and the rest are
  declined outright. That check is also what keeps this cheap: it runs first, so a summand
  this cannot speak about never reaches the limit engine.
  Last in the chain, after every closed form, so that a series which does converge is
  summed rather than tested. Asked for on the review of
  #1218, where
  integral(floor(x)^floor(x), x, 1, +oo) splits into sum(n^n, n, 1, +oo) and was
  left as written for want of this; part of
  #1212.
  

• EvaluationHomomorphism

  Summary

  Deciding that a polynomial in several variables does not factor, by evaluating
  every variable but one at an integer point and asking the one-variable factoriser.
  

  Remarks

  Substituting integers for variables is a ring homomorphism, so a factorisation survives
  it: if f = g·h then f(x, a) = g(x, a)·h(x, a). Degrees survive it too, as
  long as the leading coefficient in x does not vanish at the point — and degrees in
  x add, so if the total is preserved then neither part can have lost any. So an
  image that is irreducible, of the same degree in x, is a proof that the polynomial
  it came from is irreducible.
  The converse is not true and is not claimed. An image factors more readily than its
  source — x^2 + y at y = 4 is x^2 + 4, still irreducible, but at
  y = -4 it is (x-2)(x+2) — so a reducible image says nothing at all, and
  several points are tried before giving up. This decides one direction and declines the
  other, which is why it can be asked first and cheaply.
  Why it is worth having next to KroneckerFactorization. The
  substitution's image has degree Π (d_i + 1) - 1, a product, so it leaves the
  one-variable factoriser's reach after very few variables and the answer is a refusal —
  x^2 + y^2 + z^2 + w^2 + 1 is past it. An evaluation image has degree d_main and does not grow with the variable count at all, so the polynomials this settles are
  exactly the ones the substitution cannot reach. It answers only "it does not factor", but
  since #1059 that is
  an answer rather than a refusal.
  The precondition is checked and not assumed. The argument above is about factors
  of positive degree in x; a factor that is free of x — the content — is
  invisible to it, and y·(x + 1) would be certified irreducible on an image of
  2x + 2 whose primitive part is x + 1. So the content in the main variable is
  computed, and anything but a constant declines. The caller has a path that takes the
  content out and asks again.
  This is not Hensel lifting, and does not pretend to be the piece of
  #746 tier 1 that is
  still outstanding. It is the first step of that algorithm — choosing an evaluation point
  whose image keeps the degree and stays square-free — used for the one conclusion that
  needs no lifting. Lifting a *reducible* image back to a factorisation of the source is the
  rest of it, and is a different piece of work.
  

• ExponentialSeries

  Summary

  A summation to +oo whose summand is a polynomial in the index times a power with
  the index in the exponent, over a factorial of the index: sum(x^k / k!, k, 0, +oo) is e^x, and sum(3^(k+2) * (k^2 + k + 1) / (k + 3)!, k, 0, +oo) is
  (8 * e^3 - 41) / 6.
  

  Remarks

  The whole family is e^c. Shift the index so the factorial is j!, and the
  summand is q(j) * c^j / j! for a polynomial q; then
  sum(j^n * c^j / j!, j, 0, +oo) = e^c * T_n(c), where T_n is the Touchard
  polynomial sum(S(n, m) * c^m, m, 0, n) over the Stirling numbers of the second
  kind -- j^n written in falling factorials, each of which sums to c^m * e^c.
  A lower bound above the shifted zero subtracts the terms below it, which are finitely
  many and exact. The series converges for every c, so no condition is owed.
  Recognised structurally, on the factors of the simplified summand: exactly one
  (k + a)! ^ (-1) with a whole a, at most one c ^ (k + s) with
  c free of the index, and a polynomial in the index for the rest; anything else
  is left as written. A power whose exponent is not the index plus a constant --
  c^(2k) -- is declined rather than rewritten, and so is a base that is zero.
  The first of the orientation-week questions of
  #1212.
  

• ExpressionNumerical

• ExtremumOverSet

  Summary

  The largest or smallest value an expression takes over a set, and the points where it
  takes it: max(f(t), t in S), min, argmax, argmin.
  

  Remarks

  Over a finite set of numbers the expression is evaluated at every element and the values
  compared, which is the definition. Over a closed interval with numeric ends the extremum is
  attained at an endpoint or at a stationary point inside, so the candidates are the closed
  endpoints and the zeros of the derivative in the open interval, which the solver is asked
  for; a periodic family of zeros -- pi/6 + 2 pi n -- is read as a line in its
  parameter and the whole numbers that land inside the interval are enumerated. An open
  endpoint is not a candidate, since a value there is not attained: max(x, x in [0; 1)) has no maximum, and is left as written rather than answered 1.
  Two guards, because a wrong maximum is worse than none. The expression has to be one
  that is smooth on the reals -- sums, products, non-negative whole powers, sines, cosines,
  and exponentials with a positive base -- so that every interior extremum is a zero of the
  derivative; abs(x) has its minimum where its derivative is undefined, and
  1/x has no maximum on [-1; 1] at all. And the candidates' best value is
  checked against the expression sampled along the interval: the solver's list of zeros is
  not guaranteed complete, and a sample that beats the best candidate means one was missed,
  on which the question is left as written. A sample can miss a narrow peak, so this is a
  guard and not a proof; what it rules out is the wrong answer the incomplete list would
  otherwise give with confidence.
  The value is returned symbolically -- the expression at the best point, simplified -- and
  the points as the candidates themselves, so max(sin(t)^3 cos(t), t in [0; pi/2]) is 3 sqrt(3) / 16. Question I.6 of
  #1212.
  

• FactorialSum

  Summary

  A polynomial times the factorial of the index, summed in closed form where the sum
  telescopes: sum(k k!, k, 1, n) is (n + 1)! - 1, Sullivan and Mackey's Prob 2.7.17.
  

  Remarks

  P(k) k! is T(k + 1) - T(k) for T(k) = Q(k) k! exactly where
  (k + 1) Q(k + 1) - Q(k) = P(k), and then the sum from a to b is
  T(b + 1) - T(a). The equation is triangular in Q's coefficients from the top
  down, the coefficient of k^(m + 1) fixing q_m, and its constant term is one
  condition more: q_1 + q_2 + ... = p_0. Where that fails, no polynomial Q exists
  and the sum is declined: sum(k!, k, 0, n), the left factorial, has no closed form in
  factorials. This is Gosper's algorithm for the one family, where the certificate is a
  polynomial.
  Over a >= 0, where a! is defined; a range that runs backwards is empty and
  the sum zero, which is what the piecewise says, while the closed form at b = a - 1 is
  zero already.
  https://github.com/asc-community/AngouriMath/issues/1409
  

• Fraction

• FractionFreeDeterminant

  Summary

  Bareiss' fraction-free elimination: the determinant of a square matrix over an
  integral domain, in O(n^3) ring operations and without ever leaving the ring.
  

  Remarks

  Ordinary Gaussian elimination divides by the pivot, so over a ring of polynomials it
  produces quotients — and an expression built from them is undefined wherever a pivot
  vanishes, at points where the determinant itself is perfectly well defined. That is
  what #992 was
  about, and why Determinant used Laplace expansion rather
  than elimination.
  Bareiss divides too, and the divisions are the point: each entry is divided by the
  previous pivot, and that division is exact — the quotient is a
  determinant of a minor and therefore back in the ring. So the intermediate entries do
  not swell the way Gaussian elimination's do, and nothing is ever left as a quotient to
  exclude a point.
  Exactness is a fact about the ring, and is checked here anyway.DivideExact(AngouriMath.Functions.MultivariatePolynomial,System.Int32) returns
  null rather than a remainder, so a division that does not come out — because the term
  ceiling was reached, or because an assumption above is wrong — stops the elimination
  instead of producing an answer that is quietly not the determinant. Every caller reads
  null as "use another method", never as "there is no determinant".
  Split out of PolynomialResultant, where it was written for the Sylvester
  matrix. Shared rather than written twice, deliberately: a sign convention or an
  off-by-one in an elimination is a wrong answer that looks entirely plausible, and one
  implementation exercised by two callers is tested by both.
  #999

• GenTensorGuard

  Summary

  Makes the matrix operations that go through GenericTensor safe to call from more than one
  thread, which Multithreading documents as supported.
  

  Remarks

  GenericTensor 1.0.4 keeps two process-wide mutable statics, and neither fails loudly.
  Reported upstream as https://github.com/asc-community/GenericTensor/issues/40 with a fix in
  https://github.com/asc-community/GenericTensor/pull/41; this type is what stands in until a
  release carrying that fix exists, and it should be deleted when one does.
  
  The two need opposite treatments, because only one of them can be closed without a lock:
  
  The scratch-matrix pool behind DeterminantLaplace and Adjoint hands
  every caller the same tensor for a given size, and the caller writes into it. There is
  nothing to warm and no way to avoid it from out here, so those calls take
  ScratchPool. Measured on GenericTensor's own suite, sixty 5x5 matrices
  computed sequentially and then again in parallel: 53 of 60 Laplace determinants and 60 of
  60 adjugates came back with different values. Serialising them is the cost of not doing
  that.
  
  The compiled-operation cache behind the piecewise operators is an unsynchronised
  Dictionary, so it is only unsafe while it is being filled -- once an entry is there
  the reads are pure. That one needs no lock at all, because the set of entries this library
  can ever ask for is fixed and tiny: Matrix rejects any tensor that is
  not rank 2, and every call here uses the default single-threaded mode, so the only keys
  reachable are addition, subtraction and multiplication at rank 2. Filling all three once,
  under Lazy`1, leaves the dictionary read-only from then on.
  

• GeometricSeries

  Summary

  A summation whose summand is a power with the index in the exponent, times something free
  of the index: sum(x^k, k, 0, n) is (1 - x^(n + 1)) / (1 - x), and
  sum(2^(-k), k, 0, +oo) is 2.
  

  Remarks

  The summand is read as C * b^(m k + s), which is C b^s * r^k with the ratio
  r = b^m for a whole non-zero m. Between two bounds the sum is
  C b^s (r^a - r^(b + 1)) / (1 - r), which holds for every pair of integers with
  b >= a - 1 and every ratio but 1 -- at r = 1 the sum is the number of terms
  times the constant, and below b = a - 1 the range is empty, which this library
  answers with 0. Where the ratio is a number the branch that applies is known; where it
  is symbolic, both are offered as a piecewise, the way
  PolynomialSummation offers the empty range.
  To +oo the series converges exactly when |r| < 1, to C b^s r^a / (1 - r).
  A numeric ratio outside that is left as written -- the sum is infinite or has no value,
  and which of the two is not this reader's to say -- and a symbolic ratio carries the
  condition, since outside it the sum has no value the formula could be standing for.
  Recognised structurally, on the factors of the simplified summand: exactly one power whose
  base is free of the index and whose exponent is the index times a whole number plus
  something free of the index; every other factor free of the index. A polynomial factor in
  the index -- k x^k -- is not this family and is declined, and so is a base that is
  zero or a ratio that is a number and 1. Part of question I.2 of
  #1212, where the
  step integral of 2^(-floor(x)) leaves this sum.
  

• ImageByCalculus

  Summary

  The image of a set of reals under a quotient of polynomials, { f(x) : x in S }, read
  off the function's critical points and its limits: Sullivan and Mackey's §7.3.5 Try 1,
  x/(1 + x) over RR \ {-1}, is RR \ {1}, and Prob 7.8.8's
  (2x - 1)/(2x (1 - x)) over (0, 1) is RR.
  

  Remarks

  A continuous function maps an interval onto an interval, and a differentiable one is
  monotone between the zeros of its derivative, so the image of an interval without a pole is
  the interval between the least and the greatest of the values at the critical points inside
  it, the values at its closed ends and the one-sided limits at its open ones. An end of the
  image is closed where the value is taken, at a critical point or a closed end, and open
  where it is only approached. The set is cut into such intervals first: at the points a
  difference removes, and at the poles, where the function is not defined.
  The derivative's zeros have to be all of them, or a turning point is missed and the image
  comes out too small. So the numerator of the derivative, and the denominator whose zeros
  are the poles, have to be polynomials of degree four or less, which the solver answers in
  radicals completely; the coefficients have to be rational, so that a coefficient which
  cancels is zero rather than a residue; and every root has to evaluate, a real one to a
  candidate and a non-real one to nothing. A real root can come out of the radicals with an
  imaginary residue near 1e-99, which is read as zero below the downcasting tolerance
  whether downcasting is on or not.
  https://github.com/asc-community/AngouriMath/issues/1409
  

• IntegerPolynomial

  Summary

  A polynomial in one variable over the integers, stored densely.
  

  Remarks

  A second polynomial representation next to MultivariatePolynomial, and
  deliberately so. That one is sparse, packs eight exponents into a ulong and
  carries coefficients over Q, which is what a multivariate greatest common
  divisor wants. Factoring wants the opposite of all three: one variable, dense
  coefficient access by degree, and coefficients over Z, because every bound the
  algorithm relies on — Mignotte's on the size of a factor, the modulus a Hensel lift
  has to reach — is a statement about integers. Sharing one type between the two would
  mean paying a dictionary lookup per coefficient in the inner loop of the lift and
  re-deriving a denominator that is known to be one.
  Trailing zero coefficients are never stored, so Degree is
  coefficients.Length - 1 and the zero polynomial is the empty array with degree
  -1. Coefficients are ordered lowest power first, which is the order the rest of
  Functions/Algebra/Polynomials already uses.
  

• IntervalArithmetic

  Summary

  The image of an interval under a function that is monotone on it, and the product and
  quotient of two intervals: what ln((0; 1)), e^[0; 1], [1; 2]^2 and
  (1; 2) * (3; 4) are as sets.
  

  Remarks

  A function that is monotone on an interval maps it to the interval between the images of
  its ends, in the same order when it is increasing and the reverse when it is decreasing,
  each end attained exactly when the end it comes from is -- so the openness travels with
  the end. An end whose image is infinite is never attained: ln((0; 1)) is
  (-oo; 0), and ln([0; 1)) is the same set, since ln(0) is not a
  value. That is the whole of the method, and the only question for each function is on
  which intervals it is monotone, which is answered here for the ones the library has
  nodes for and declined for the rest: a sine over an interval longer than half a period
  is not an interval between two images, and a sign that cannot be read is not guessed.
  Only numeric ends are read. An interval with a symbolic end could be handled by the same
  rule under a condition on the end, and is left as written instead: the answer would be
  a piecewise over the sign of something, which is not what a caller asking for a set
  wants back.
  A product of two intervals is the interval between the least and the greatest of the
  four products of ends, an end attained where both its factors are, and a quotient is a
  product by the reciprocal, which is an interval exactly when the divisor does not
  contain zero.
  https://github.com/asc-community/AngouriMath/issues/322
  

• InverseTrigonometricTableValues

  Summary

  The trigonometric tables read backwards: given a value, the angle in the principal
  range whose sine or tangent it is.
  https://github.com/asc-community/AngouriMath/issues/569
  https://github.com/asc-community/AngouriMath/issues/179
  

• IversonSum

  Summary

  A sum of an Iverson bracket over a range of whole numbers is a count, written in closed
  form: how many whole numbers of the range satisfy the statement. A product of brackets is
  the bracket of the conjunction.
  sum(iverson(2 divides k or 3 divides k), k, 1, 1000) is 667.
  

  Remarks

  The statement is read as conditions on the index. An equation linear in it fixes it at a
  point p, and then the sum is a bracket again, of p being whole, in the range,
  and satisfying the other conditions: in a nested sum that is what the next sum out counts.
  A comparison linear in the index, with a numeric slope, bounds it from one side, and so
  does a membership in an interval. A divisibility of a linear function of the index with
  whole coefficients fixes its residue, and several residues combine into one class or
  none, by the Chinese remainder theorem. A conjunct that does not mention the index is a
  factor, and so is a linear function of it being whole, which depends only on its constant
  term. What is left is the number of whole numbers from L to U in the class
  r modulo m, floor((U - r)/m) - floor((L - 1 - r)/m), or
  U - L + 1 with no class, and never below zero, which is also the count of an empty
  range. A bound that is not a number is read as real, as a bound of the range that is not a
  number is read as whole.
  A negation and a disjunction are counted by inclusion and exclusion: not Q counts
  the range less Q, and Q or R counts Q and R less both. So
  sum(iverson(not 2 divides k and not 5 divides k), k, 1, 99) is 40, Sullivan and
  Mackey's §8.7.4 Try 1.
  https://github.com/asc-community/AngouriMath/issues/1409
  https://github.com/asc-community/AngouriMath/issues/1478
  

• KroneckerFactorization

  Summary

  Factorisation of a polynomial in any number of variables, by reducing it to one variable
  and putting the answer back.
  

  Remarks

  Kronecker's substitution, in mixed radix. A factor of a polynomial has degree at
  most d_i in each variable v_i, because a factor divides it. So with radices
  d_i + 1 and place values s_0 = 1, s_(i+1) = s_i * (d_i + 1), the map
  v_0^e_0 · … · v_(k-1)^e_(k-1) -> t^(Σ e_i · s_i) writes each exponent as one digit
  of a numeral and is therefore injective on every monomial that can appear in the
  polynomial or in any of its factors. A factorisation of the one-variable image can be read
  back digit by digit, and each subset of its irreducible factors names a candidate.
  A candidate is a guess and is checked by division. The image can factor further
  than the polynomial does — the substitution is injective on monomials, not on
  factorisations — so a subset whose product reads back as a polynomial need not divide the
  original. Every one is tested with exact division before it is kept, which is why this
  cannot answer wrongly: the worst it does is fail to find a factorisation that exists and
  say so.
  What it will not do. The image has degree Π (d_i + 1) - 1, a *product* and
  not a sum, and the one-variable factoriser stops at
  MaxDegree — so the ceiling closes quickly as variables are
  added. Two variables reach bidegrees like (2, 10), (3, 7) and (5, 4); three variables of
  degree 2 fit (27 ≤ 32) and four do not (81); and a quadratic in eight variables is far
  past it. The recombination is over subsets, so the number of irreducible factors of the
  image is capped as well. Both limits are refusals, never wrong answers.
  Raising the degree ceiling is not what would lift them, and that was measured rather
  than assumed.MaxDegree is 32 while the machinery
  underneath affords 64 (MaxDegree), which looks like
  a free doubling of the exponent budget — a whole variable's worth of reach, since the
  budget is a product. Doubled, nothing new factors: x^7 - y^7,
  x^6 - y^6, x^3 - (y + z)^3, (x^8 + y)(x^8 + 3y) and
  (x^2 + y^5)(x^2 - y^5) all still refuse, at images of degree 34 to 56 that are
  inside the raised ceiling.
  The reason is the method rather than the bound: the substitution's images over-factor
  badly. A two-factor bivariate maps to a one-variable polynomial that splits into many
  irreducibles — x^7 - y^7 becomes t^7 (1 - t^49), whose factors are
  cyclotomic — so the recombination is exponential in a factor count the substitution itself
  inflates. That is exactly the cost MaxDegree is set to
  bound, and moving it only moves where the refusal comes from. Lifting these limits means
  not inflating the factor count in the first place, which is Hensel lifting with an
  evaluation homomorphism — a different algorithm, not a larger number
  (#746 item 43).
  

• MonomialOrder

  Summary

  Which monomial is the leading one.

• MonomialProduct

  Summary

  A product whose body is a monomial in the index, written in closed form:
  product(k, k, 1, n) is factorial(n).
  

  Remarks

  The sibling of PolynomialSummation and a narrower thing than it, because a
  product has no linearity to take apart: a sum of two terms is the sum of their sums, and a
  product of two terms is not the product of their products in any way that helps. What is
  left is the body that is a single term — c * k^p — over which the product
  separates into a power of the constant and a power of the factorial.
  The condition is the same one, for the same reason. An empty range multiplies to
  1, so product(k, k, 1, n) is 1 at every n < 1, while
  factorial(n) is not — it is undefined at the negative integers, being the gamma
  function's poles. Answering the one with the other unconditionally would turn a value into
  an undefinedness, which is the failure the contract's O4 is about. The identity holds
  where to >= from - 1, and that is what is attached.
  A positive lower bound where the index is in the body, and that one cannot go in the
  condition. product(k, k, a, b) is b! / (a-1)! only where a >= 1; below
  that the range runs through zero and the product is 0, while (a-1)! is
  undefined. But a < 1 does not mean the range is empty, so it cannot share a
  branch with the empty-range case — a piecewise saying "identity otherwise" would be wrong
  there. So it is decided before anything is built, and a lower bound that is not a concrete
  integer of at least one is declined instead. A constant body has no such restriction,
  there being no factorial in its answer.
  

• MultivariatePolynomial

  Summary

  A polynomial in several variables over the rationals, stored sparsely.
  

  Remarks

  The coefficient domain is deliberately only Q. A polynomial whose
  coefficients are arbitrary expressions is not one this can reason about: deciding
  whether sqrt(2) - a is zero is as hard as the problem that sent us here, and
  a divisor wrongly believed nonzero produces a wrong cancellation rather than a
  missing one. Anything outside Q is refused at the door by
  TryParse(AngouriMath.Entity,System.Collections.Generic.IReadOnlyDictionary{AngouriMath.Entity.Variable,System.Int32}).
  An exponent vector is packed into one UInt64, a byte to a variable,
  the first variable in the most significant byte. Comparing packed monomials is then
  exactly the lexicographic order on exponents that DivideExact(AngouriMath.Functions.MultivariatePolynomial,System.Int32) needs,
  and looking a monomial up costs one hash.
  This and its neighbours in Functions/Algebra/Polynomials are kernel algebra:
  the solvers, the evaluator and the simplifier all depend on them, and they depend on
  none of those. That direction is the point of the folder. PolynomialGcd in particular is reached from simplification, from Core/Transformations and
  from evaluation, which is why it lived under Functions/Simplification for as
  long as simplification was the only caller anybody had counted.
  Partial so that the operations only a Gröbner basis needs — monomial divisibility, an
  order other than lexicographic, reduction against a set — live beside the solver that
  wants them, in Functions/Algebra/Groebner, rather than here where every other
  caller would have to read past them. See MultivariatePolynomial.Groebner.cs.
  

• NumericContent

  Summary

  The whole number every term of a sum divides by, taken out in front of it:
  2x + 4a is 2 * (x + 2a).
  

  Remarks

  #195, and the reason
  it says "forcefully… but not peacefully". The rules already take out a factor that appears
  identically in every term — 2x + 2a is 2 * (a + x) under plain
  Simplify(System.Int32) — and that is what "peacefully" means here. A factor that
  is only a common divisor is different: 2 * (x + 2 * a) is one node larger than
  4 * a + 2 * x, so SimplifiedRate will not choose it and Simplify should
  not offer it.
  So this runs in Factorize(System.Int32) and nowhere else. That is already the
  forceful half of the pair — the call a user makes when they have decided they want the
  factored form, whatever it rates — and putting it there needs no new mode and leaves
  Simplify untouched.
  Whole numbers only, and a positive one. Rational coefficients have a common divisor
  too — x/2 + a/3 over 1/6 — but taking it out puts a quotient outside the sum
  rather than a factor, which is a different rewrite and arguably the wrong direction. And the
  sign is left inside: -2x - 4a becomes 2 * (-x - 2a) rather than
  -2 * (x + 2a), because deciding which of those is wanted is a second question and
  this answers the first one.
  

• PartialFractions

  Summary

  One step of a partial fraction decomposition, at a coprime pair of factors of the
  denominator rather than at a root of it.
  

  Remarks

  The sibling step, TrySplitOffRationalRoot(AngouriMath.Entity,AngouriMath.Entity,AngouriMath.Entity.Variable,AngouriMath.Entity@,AngouriMath.Entity@,AngouriMath.Entity@), splits at a
  rational root, which is all the decomposition there was: a denominator with no rational
  root was left whole, so 1/(x^4 + 3x^2 + 2) had no antiderivative even though it
  is (x^2 + 1)(x^2 + 2) and both of those are integrated by the rule for a linear
  numerator over a quadratic. Nothing was missing but the split.
  https://github.com/asc-community/AngouriMath/issues/919
  One step and not the whole decomposition, for the same reason as the sibling: what comes
  out is two strictly smaller problems of the same kind, and the integrator recurses into
  them. Splitting D into coprime A and B, the extended Euclidean
  algorithm gives U*A + V*B = 1, so N = N*V*B + N*U*A and
  N/(A*B) = N*V/A + N*U/B. Each numerator is then reduced modulo its own
  denominator; the polynomial parts that come off cannot survive, since a proper fraction
  minus two proper fractions is a polynomial that vanishes at infinity.
  No condition is owed.A and B being coprime, A*B is zero
  exactly where one of them is, so the two sides are undefined at the same points and the
  domain neither widens nor narrows. That is what makes this different from cancelling a
  shared factor, which is where a decomposition usually loses a singularity.
  The decomposition is produced only where every piece of it is a shape an integration
  rule reads — see the guard below, which is what keeps declining cheap. A denominator
  that is a power of one irreducible is declined for the further reason that it has no
  coprime pair to split into at all. The ladder that decomposes that one — N/f^k as terms over f^k, f^(k-1), ... — is deliberately not built here: for
  f linear the sibling step already does it, and for f quadratic every term
  it produces is over (x^2 + c)^k, which nothing reads, so the decomposition would
  end in the same unevaluated integral it started from.
  

• Patterns

• PolynomialDeterminant

  Summary

  The determinant of a matrix whose entries are polynomials over the rationals, by
  Bareiss' fraction-free elimination — O(n^3) where Laplace expansion is
  O(n!).
  

  Remarks

  Laplace is not merely slower. For a fully symbolic matrix it is optimal, because
  the determinant genuinely has n! terms and no algorithm returns it smaller in
  expanded form. For a numeric one it is pure waste: the answer is a single number
  and O(n^3) work suffices. That is the split
  #999 asks for, and
  what decides it is not the size but whether the entries are polynomials this can read —
  which is settled per matrix, by trying, rather than by a rule about n.
  Why this cannot introduce a condition. Bareiss divides, and the usual reason to
  distrust an elimination is that its divisions leave quotients excluding the points where
  a pivot vanishes — the defect
  #992 was about. Its
  divisions are exact over an integral domain, and here they are exact and checked:
  the arithmetic happens in MultivariatePolynomial, which has no quotients to
  leave behind at all, and a division that does not come out returns null and sends the
  caller to Laplace. So the answer is a polynomial in the entries, or it is Laplace's.
  What it declines. An entry that is not a polynomial over the rationals — anything
  with sin, a symbolic exponent, a genuine 1/x — a matrix in more than
  MaxVariables indeterminates, and a matrix mentioning
  a Constant, since e and pi are values rather than
  indeterminates and this ring cannot hold them. Each is a refusal to try, not a wrong
  answer, and Laplace answers them exactly as before.
  

• PolynomialFactoring

  Summary

  Factors a polynomial in one variable into linear factors with whole roots:
  x^2 + 2x + 1 becomes (x + 1)^2, and
  x^3 - 6x^2 + 11x - 6 becomes (x - 1)(x - 2)(x - 3).
  

  Remarks

  Deliberately narrow, on two counts.
  Rational roots only. Factoring through every root would answer
  (x - i)(x + i) for x^2 + 1 and (x - sqrt(2))(x + sqrt(2)) for
  x^2 - 2, which is not what anyone means by factoring those.
  And only when the polynomial splits completely into whole roots. A partly factored
  answer is not obviously better than the sum it came from, and fractional roots turn
  up mostly in the output of calculus, where the expanded form is the conventional
  one: the antiderivative of x^2 + x reads better as x^3/3 + x^2/2 than
  as x^2 * (x + 3/2) / 3.
  What comes out of here is a candidate, not a decision. The simplifier keeps it
  alongside the other forms it has found and picks between them by its complexity
  metric, which is why x^2 - 1 stays as it is while (x + 1)^2 wins.
  

• PolynomialFactorization

  Summary

  Factors a polynomial in one variable over the rationals into irreducibles:
  x^4 + 3x^2 + 2 becomes (x^2 + 1)(x^2 + 2), which no search for roots can
  find because it has none.
  

  Remarks

  This is what PolynomialFactoring is not. That one tries the candidates of
  the rational root theorem and divides out the linear factors it finds, which answers
  the question only when the polynomial splits into linear pieces. A factor of degree two
  or more with no rational root is invisible to it, and those are the common case above
  degree three.
  The route is Zassenhaus's, in four steps. Clear denominators and take the primitive
  part, so the problem is over Z. Split off the repeated factors with
  SquareFreeDecomposition, so every remaining problem is square-free.
  Factor what is left modulo a small prime, where
  Berlekamp answers completely and cheaply.
  Then lift that factorisation from p to p^k by Hensel's construction and
  try products of the lifted pieces against the original, which is where the true
  factors are recovered — an irreducible factor over Z may well split further
  modulo p, so the modular factors have to be recombined rather than read off.
  Zassenhaus, On Hensel factorization I, J. Number Theory 1 (1969); von zur Gathen
  and Gerhard, Modern Computer Algebra, ch. 15.
  Two things bound the cost, and both are refusals rather than approximations. The
  recombination is exponential in the number of modular factors, so it is given a budget
  and declines past it. And k is chosen from Mignotte's bound so that a
  coefficient in the symmetric range modulo p^k is the coefficient itself; a
  smaller k would not make an answer wrong, since every candidate is confirmed by
  exact division over Z before it is accepted, but it would make the search miss
  factors and call a reducible polynomial irreducible.
  Nothing here is trusted. Every candidate factor is divided out exactly over Z,
  and the factors are multiplied back and compared with what they came from before the
  answer is returned. The failure mode that survives all of that is an incomplete
  factorisation, never a wrong one.
  

• PolynomialGcd

  Summary

  The greatest common divisor of two polynomials in several variables over the
  rationals, and the cancellation of a quotient that it makes possible:
  (x^2 + 2xy + y^2) / (x^2 - y^2) is (x + y) / (x - y) (#55).
  

  Remarks

  A polynomial in several variables is a polynomial in one of them whose coefficients
  are polynomials in the rest, so the algorithm is the univariate one applied down a
  recursion on the variable count. What it cannot be is the plain Euclidean algorithm
  over that coefficient ring: pseudo-division multiplies through by the leading
  coefficient every step, and the coefficients of the remainder sequence then grow
  exponentially in the degree. The classic example is Knuth's, where two degree-8
  polynomials over the integers produce a remainder with a coefficient near 10^35.
  Two things keep that in hand, and both are needed. The greatest common divisor
  splits as the gcd of the contents times the gcd of the primitive parts, because the
  content carries everything free of the main variable and the primitive parts carry
  nothing of it; so the content is taken out first, recursively, in one variable
  fewer. And within the remainder sequence the subresultant coefficients are divided
  out at each step — that division is exact, since what is left is a subresultant, and
  it is what turns exponential growth into linear. Knuth, TAOCP vol. 2,
  §4.6.1, algorithms C and E; Geddes, Czapor and Labahn, Algorithms for Computer
  Algebra, §7.3.
  Nothing here trusts the result of that machinery. The divisor it computes is
  divided out of both sides and multiplied back, and the quotient is only used when
  both come out equal to what they started as. A divisor that is merely common and
  not greatest costs an incomplete cancellation; one that is not a divisor at all
  would be a wrong answer, and is the thing the check is there to stop.
  

• PolynomialGeometricSeries

  Summary

  A summation whose summand is a polynomial in the index times a power with the index in
  the exponent: sum(k 2^k, k, 1, n) is (n - 1) 2^(n + 1) + 2, and
  sum((-1)^(k - 1) k^2, k, 1, n) is (-1)^(n - 1) n (n + 1)/2, which is
  §5.3.4 Try 6 of Sullivan and Mackey's An Introduction to Proofs.
  

  Remarks

  The summand is read as p(k) C b^(m k + s), which is C b^s p(k) r^k with the
  ratio r = b^m, the way GeometricSeries reads its summand, with a
  polynomial p of degree at least one beside the power. For a ratio other than 1
  there is a polynomial q of the same degree with q(k + 1) r - q(k) = p(k),
  so that q(k) r^k is a discrete antiderivative of the summand, and the sum from
  a to b is q(b + 1) r^(b + 1) - q(a) r^a. The coefficients of
  q are found highest first: the coefficient of k^j in q(k + 1) r - q(k) is (r - 1) q_j + r sum_{i > j} binomial(i, j) q_i, one division by r - 1 each, which is the whole of the linear algebra -- Gosper's algorithm specialised to a
  summand whose ratio of consecutive terms is a rational function with a constant
  denominator.
  At r = 1 the summand is the polynomial, which PolynomialSummation answers; a symbolic ratio carries provided not r = 1, since the formula divides
  by r - 1. To +oo the series converges exactly when |r| < 1, to
  -q(a) r^a, since q(k) r^k then goes to zero. Part of
  #1409.
  

• PolynomialResultant

  Summary

  The resultant of two polynomials in several variables over the rationals, and the
  discriminant that follows from it. Eliminating a variable between two equations is
  what these are for: Res(f, g) taken in y vanishes exactly where
  f and g have a common y, so it is the condition on the
  remaining variables that the pair be solvable.
  

  Remarks

  The resultant is defined here as the determinant of the Sylvester matrix, and it is
  computed as one. That is deliberate. The remainder-sequence formulations are faster,
  but each carries a factor (-1)^k and a power of a leading coefficient that has
  to be tracked through every step, and a sign convention got wrong there is a wrong
  answer that looks entirely plausible. Taken as a determinant, the sign convention is
  the one property that cannot be got wrong: Res(f, g) = (-1)^(deg f * deg g)
  Res(g, f) and Res(f, g) = lc(f)^deg g * lc(g)^deg f * prod (a_i - b_j) both fall out of the matrix rather than being imposed on it.
  The determinant is taken by one-step fraction-free elimination, which is the same
  idea as the subresultant remainder sequence in PolynomialGcd and for
  the same reason: every intermediate entry is a minor of the original matrix, so the
  division at each step comes out exact and the coefficients stay the size of those
  minors instead of compounding. Bareiss, Sylvester's identity and multistep
  integer-preserving Gaussian elimination, Math. Comp. 22 (1968); Geddes, Czapor
  and Labahn, Algorithms for Computer Algebra, §9.3; Knuth, TAOCP vol. 2,
  §4.6.1.
  The degenerate cases are the ones implementations usually differ on, and these were
  measured against SymPy 1.14 rather than recalled: a zero argument gives zero whatever
  the other side is, two arguments free of the main variable give one, and
  Res(f, c) = c^deg f. All three are what the Sylvester matrix already says once
  a polynomial free of the main variable is read as having degree zero — the matrix is
  then diagonal, or empty, and an empty determinant is one.
  Part of the polynomial layer of
  #746, item 43.
  

• PolynomialSummation

  Summary

  A summation whose summand is a polynomial in the index, written as a polynomial in the
  bounds: sum(k, k, 1, n) is n^2/2 + n/2.
  

  Remarks

  The operator writes itself out term by term where the bounds are concrete and few, and
  otherwise stayed as written — so a symbolic bound had no answer at all, and neither did a
  concrete range past a hundred terms. Both are the same gap: a sum of a polynomial has a
  closed form, and computing it is cheaper than the expansion it replaces.
  No Bernoulli numbers. The sum of a degree-d polynomial in the index is a
  polynomial of degree d + 1 in the bound, which is the whole of what is needed: a
  polynomial of that degree is determined by d + 2 of its values, and those values
  are sums of d + 2 terms each, computed directly. Interpolating them recovers the
  coefficients exactly, in rational arithmetic, with no table to carry and no identity to
  get subtly wrong. Faulhaber's formula would give the same answer by a shorter route that
  needs Bernoulli numbers, which the library does not have.
  The condition is not decoration.sum(k, k, 1, n) is notn^2/2 + n/2 for every n: at n = -2 the range is empty and this
  library answers an empty range with 0, while the polynomial gives 1. The
  identity holds exactly when to >= from - 1, so that is what is attached, with the
  empty-range value as the other branch. Where the bounds are concrete the condition is
  decidable and the piecewise collapses to a number.
  SymPy answers the same input with the bare polynomial and is not making a mistake: it
  reads a reversed range as the negated sum over the flipped one, under which the identity
  is unconditional. This library defines an empty range as the operator's identity instead,
  and the condition is what that choice costs.
  

• PredicateEntailment

  Summary

  Whether one predicate being true forces another to be true, decided structurally and
  only where it can be proven.
  

  Remarks

  Written for Piecewise, which takes its first matching case and can
  therefore drop any case whose predicate entails an earlier one: wherever the later
  predicate holds the earlier one holds too, so the earlier case is taken and the later is
  unreachable. That rule was already applied for predicates that are equal; this is
  the same rule with a wider notion of "already covered".
  One-directional and deliberately incomplete. Entailment between arbitrary predicates
  is not decidable, so the only answers here are "proven" and "not proven", and the second is
  answered false. A false negative costs a case that could have been
  dropped, which is a longer answer; a false positive would delete a reachable case, which is
  a wrong one. Everything below is therefore a sufficient condition, never a heuristic.
  Three-valued logic does not complicate it. A case is *taken* only when its predicate
  is true, so the only thing that has to hold is that a true antecedent forces a true
  consequent. What either predicate does when it is NaN — over a non-real argument, say
  — never arises, because a case with a NaN predicate is not taken either way.
  Part of question I.3 of
  #1212, where
  distributing a binder over a piecewise produces one case per subset of the conditions and
  most of them are unreachable.
  

• PrimeFieldFactorization

  Summary

  Factorisation of a monic square-free polynomial over the prime field F_p into
  monic irreducibles, by Berlekamp's algorithm.
  

  Remarks

  The algorithm rests on one observation. Raising to the p-th power is a field
  automorphism fixing F_p pointwise, so on the quotient ring F_p[x]/(f) it is a linear map, and the polynomials it fixes — the Berlekamp subalgebra{ v : v^p = v mod f } — form a vector space. By the Chinese remainder theorem
  F_p[x]/(f) is the product of the fields F_p[x]/(f_i) over the
  irreducible factors of f, and in each of those the fixed elements are exactly
  the constants. So the subalgebra is a product of r copies of F_p, its
  dimension is r, and that dimension is the number of irreducible
  factors — which is what gives the loop below an exact termination test rather than a
  heuristic one. Knuth, TAOCP vol. 2, §4.6.2, algorithm B; von zur Gathen and
  Gerhard, Modern Computer Algebra, §14.8.
  Given a v in that subalgebra, v^p - v = prod_{s in F_p} (v - s) vanishes modulo f, and the factors on the right are pairwise coprime, so
  f = prod_s gcd(f, v - s). A v that is not constant takes different
  values in different components and therefore separates them; running over a basis of
  the subalgebra separates all of them.
  Berlekamp rather than Cantor–Zassenhaus, and the reason is not speed — for a large
  modulus Cantor–Zassenhaus wins, because it replaces the O(p) sweep over
  s with a random probe. It is that Cantor–Zassenhaus is randomised, and design
  principle 3 of
  #746 requires
  the same input to give the same answer on every platform and in every thread count.
  Berlekamp is deterministic by construction: the matrix, its null space and the sweep
  over s are all fixed by the input.
  The price is that the sweep costs O(p n^3) field operations in the worst case,
  linear in the modulus, so this is only sensible for a small one — hence
  MaxPrime. That is not a restriction in practice, because the caller
  chooses the modulus: factoring over the integers means picking a prime at which the
  polynomial stays square-free and lifting the result, and there is no reason for that
  prime to be large.
  

• PrimeFieldPolynomial

  Summary

  A univariate polynomial over the prime field F_p, stored densely as its
  coefficients with the constant term first.
  

  Remarks

  The point of a prime field is that it is a field with no growth in it. Over the
  rationals the Euclidean algorithm is unusable directly because the coefficients of
  the remainder sequence explode — which is why PolynomialGcd has to
  carry the whole subresultant apparatus. Here every coefficient is one machine word
  no matter how long the computation runs, so the textbook algorithms are the ones
  that are actually used: plain Euclid for the greatest common divisor, plain long
  division, square-and-multiply for powers.
  That is what makes the field the working surface for factorisation. A polynomial
  over the integers is factored by factoring it modulo a prime, where the problem is
  finite, and lifting the result back — von zur Gathen and Gerhard,
  Modern Computer Algebra, ch. 14, and Knuth, TAOCP vol. 2, §4.6.2.
  PrimeFieldFactorization is the first half of that.
  Arithmetic is Int64 throughout, and every product of two reduced
  coefficients has to fit without overflow. A reduced coefficient is at most
  p - 1, an accumulator holds at most another p - 1 before the next
  reduction, so the largest intermediate is p(p - 1) and the field is bounded
  by MaxPrime accordingly. Nothing here uses a wider type, because
  factorisation moduli are three digits and paying EInteger for them on
  the inner loop would be the wrong trade.
  Instances are immutable, and the coefficient array of a live instance is never
  written to after construction; the operations all build a fresh array. That is what
  lets Coefficients hand the array out rather than copying it.
  The modulus is required to be prime and this does not check it, because a check
  costs O(sqrt p) on every construction and every caller inside the library
  knows its own modulus. Where a composite one does reach the arithmetic it surfaces
  as a failure to invert rather than as a wrong answer, and
  Factor(AngouriMath.Functions.PrimeFieldPolynomial) — the one entry point a modulus could
  arrive at from outside — checks primality itself.
  

• Primes

• RationalFunction

  Summary

  A canonical form for rational functions over Q: two expressions denoting the
  same quotient of polynomials become the identical tree, so that deciding whether they
  are equal is a structural comparison rather than a search.
  

  Remarks

  This is the part of the language where a canonical form is possible. There is
  none for the whole of it — zero-equivalence is undecidable once pi, the
  exponential, the trigonometric functions and abs are in play (Richardson, 1968)
  — so the boundary is in the signature: a refusal means "not a rational function over
  Q, and no canonical form is claimed", never a normalisation that resembles one.
  Docs/Contributing/CanonicalForm.md is the specification.
  #934.
  Four steps, and only the first is new. The expression is gathered into a single
  quotient — nothing else in the library does that, and without it 1/x + 1/y and
  (x + y)/(x*y) could never meet. Then the numerator and denominator are divided
  by their multivariate greatest common divisor, which
  PolynomialGcd computes and verifies. Then both are scaled so that the
  denominator's leading coefficient is one, which is what makes 2x/(4y) and
  x/(2y) the same tree. Coefficients are in lowest terms throughout.
  The domain is preserved rather than assumed away. Cancelling a common factor
  widens the domain — x/x is not 1 — so where a factor of positive degree
  is cancelled the answer carries the condition that it is nonzero, which is what the
  library already does elsewhere and what keeps "equal trees means equal expressions"
  true rather than nearly true. Gathering over a common denominator does not widen
  anything: a sum is defined exactly where its terms are, and the product of the
  denominators vanishes exactly where one of them does.
  

• RationalPolynomial

  Summary

  A polynomial in one variable over the rationals, stored densely.
  

  Remarks

  A third polynomial representation, next to IntegerPolynomial and
  MultivariatePolynomial, because division is the operation this one exists
  for. Factoring works over Z, where content, primitive parts and Mignotte's bound
  all mean something; a partial fraction decomposition works over Q, where every
  polynomial can be divided by any other and the extended Euclidean algorithm terminates
  with a genuine unit. Doing that over Z means carrying a scaling factor beside
  every intermediate, which is where the sign and content errors live.
  Trailing zero coefficients are never stored, so Degree is
  coefficients.Length - 1 and the zero polynomial is the empty array with degree
  -1. Coefficients are lowest power first, the order the rest of
  Functions/Algebra/Polynomials uses.
  Every coefficient is reduced to lowest terms as it is written. ERational does not do that on its own, and a remainder sequence that leaves it undone multiplies
  numerator and denominator up at every step: the ratios stay correct and become
  arbitrarily expensive to compare, which is the failure that looks like a hang.
  

• ResidueClasses

  Summary

  The residue classes modulo n as sets, and the arithmetic Sullivan and Mackey's proofs book does on them:
  a class is written { x in ZZ : x = r (mod n) }, with r in [0, n), and
  that is what solving a linear congruence answers, what two congruences intersect to by
  the Chinese remainder theorem, and what an interval cuts a finite set out of.
  

  Remarks

  A multiplicative inverse modulo n is a class, never a number 1/a: the
  representative in [1, n - 1] is what Inverse(PeterO.Numbers.EInteger,PeterO.Numbers.EInteger) gives, and nothing where
  a and n share a factor, since then a x = 1 (mod n) has no solution.
  A linear congruence a x = b (mod n) is solved through the gcd: with
  g = gcd(a, n) it has solutions exactly when g divides b, and they form
  one class modulo n / g. Two classes x = a (mod m), x = b (mod n) meet
  in one class modulo lcm(m, n) when a = b (mod gcd(m, n)) and nowhere
  otherwise, which is the Chinese remainder theorem with the coprime case as the case
  where the condition is empty.
  https://github.com/asc-community/AngouriMath/issues/1409
  

• RootExtraction

  Summary

  Writes a rational raised to a rational power as a whole part times a radical that has
  nothing left to give up, so that sqrt(12) is 2 * sqrt(3) and sqrt(1/2) is sqrt(2) / 2.
  https://github.com/asc-community/AngouriMath/issues/281
  

• Simplificator

• SingleQuotient

  Summary

  Writes an expression as one quotient: a numerator and a denominator with no division
  anywhere inside either.
  

  Remarks

  This is what other systems call together or ratsimp, and it is deliberately
  not part of Simplify(System.Int32). Putting a sum over a common
  denominator makes some expressions worse — 1/x + 1/y is easier to read than
  (x + y)/(x*y) — which is why every system that has it keeps it as an operation you
  ask for. Simplify here combines nothing: a + b/c comes back as a + b/c.
  https://github.com/asc-community/AngouriMath/issues/1239
  What it is for. Everything that takes a rational function apart —
  PartialFractions and the integrator's rational path — wants its input as a
  single Divf of two polynomials, and declines anything else. So a rewrite that
  produces a correct but nested answer is thrown away one step short of being usable. The
  half-angle substitution is the case that exposed it: 1/(1 - sin(x)) rewrites to
  2/((t^2 + 1)(1 + (-2)t/(t^2 + 1))), which is 2/(t^2 - 2t + 1) after one
  distribution and is integrated at once, and was declined for want of it.
  No cancellation. The two halves are returned as built, with no common factor taken
  out: x/x comes back as (x, x) and not as (1, 1). Cancelling needs a
  gcd, which needs to know what the expression is a polynomial in, and this runs
  before anything has decided that. The callers here divide out afterwards anyway, and a
  caller that wants the tidy form asks the simplifier for it.
  It always terminates and never grows without bound, because it recurses only into
  the operands of the node it is given and each recursion is on a strictly smaller tree. What
  it can do is make the tree bigger — combining a sum of n quotients multiplies the
  denominators — so Of(AngouriMath.Entity) is a transformation to ask for rather than one to apply
  on the way past.
  

• SquareFreeDecomposition

  Summary

  Splits a polynomial into square-free parts: f = a_1 * a_2^2 * a_3^3 * ... with
  each a_i square-free and any two of them coprime.
  

  Remarks

  The first step of every factorisation, and useful on its own. A repeated factor is
  exactly a factor shared with the derivative — (x - r)^k contributes
  (x - r)^(k-1) to f' — so gcd(f, f') collects every repetition and
  dividing by it leaves each distinct factor standing once. That is why factoring only
  ever has to deal with square-free input, and why a square-free routine is worth having
  before the factoriser that consumes it.
  Yun's algorithm rather than the older Tobey-Horowitz one: both start from
  gcd(f, f'), but Yun's carries the derivative quotient forward so that each
  round's greatest common divisor is taken between polynomials whose degrees have
  already fallen, instead of re-dividing the original every time. The cost is one extra
  subtraction a round and the saving is an order of magnitude on high multiplicities.
  Yun, On square-free decomposition algorithms, SYMSAC '76; Geddes, Czapor and
  Labahn, Algorithms for Computer Algebra, §8.1.
  Characteristic zero only. Over F_p the derivative of x^p vanishes and
  the argument above breaks, which is why the finite-field side handles its own
  square-free step rather than calling this.
  

• SumOverSet

  Summary

  The value of a sum over a set, sum(f(x), x in S): the terms written out and added
  where the members of S are known and there are finitely many of them, and the sum
  left as written otherwise.
  

  Remarks

  A sum over a set counts each member once, which is what makes it well defined without an
  order: a set has no first member, and addition does not care. So the members have to be
  known to be distinct before they are added, and a listed set is read only where its
  elements are numbers. sum(x, x in { a, b }) is a + b when a and
  b differ and a when they are equal, and nothing here can tell which, so it is
  left as written.
  The sum over the roots of a polynomial is the case the node exists for:
  sum(f(w), w in { w : p(w) = 0 }). Where every root is rational, a root of a
  quadratic or a root of a binomial, the solver writes them and they are added; every is checked, by counting the distinct roots it gave against the degree of the square-free
  part of p, which is how many distinct roots p has. The roots of an
  irreducible cubic or quartic are not written out in radicals, which read no more simply
  than the sum. A root set the solver answers only in part is left as written, since a sum
  that misses a term is a wrong answer. Evaluated to a number, the roots the solver cannot
  write are found to the working precision, all of them or none, by
  DurandKerner. And a sum over a set that is not finite -- an
  interval, the integers -- is a series, which is not this node's to answer.
  #1285

• TreeAnalyzer

• TrigonometricAngleExpansion

• TrigonometryTableValues