Integer relations

Math Topics A - Z listing


Integer relations Topics

Sort by:

Frobenius number

The Frobenius number is the largest value for which the Frobenius equation(1)has no solution, where the are positive integers, is an integer, and the solutions are nonnegative integer. As an example, if the values are 4 and 9, then 23 is the largest unsolvable number. Similarly, the largest number that is not a McNugget number (a number obtainable by adding multiples of 6, 9, and 20) is 43.Finding the Frobenius number of a given problem is known as the coinproblem.Computation of the Frobenius number is implemented in the Wolfram Language as FrobeniusNumber[a1, ..., an].Sylvester (1884) showed(2)(3)

Stöhr sequence

Let and define to be the least integer greater than which cannot be written as the sum of at most addends among the terms , , ..., . This defines the -Stöhr sequence. The first few of these are given in the following table.OEIS-Stöhr sequence2A0336271, 2, 4, 7, 10, 13, 16, 19, 22, 25, ...3A0264741, 2, 4, 8, 15, 22, 29, 36, 43, 50, ...4A0510391, 2, 4, 8, 16, 31, 46, 61, 76, 91, ...5A0510401, 2, 4, 8, 16, 32, 63, 94, 125, 156, ...

Knapsack problem

Given a sum and a set of weights, find the weights which were used to generate the sum. The values of the weights are then encrypted in the sum. This system relies on the existence of a class of knapsack problems which can be solved trivially (those in which the weights are separated such that they can be "peeled off" one at a time using a greedy-like algorithm), and transformations which convert the trivial problem to a difficult one and vice versa. Modular multiplication is used as the trapdoor one-way function. The simple knapsack system was broken by Shamir in 1982, the Graham-Shamir system by Adleman, and the iterated knapsack by Ernie Brickell in 1984.

Integration problem

Let be a set of expressions representing real, single-valued partially defined functions of one real variable. Let be the set of functions represented by expressions in , where contains the identity function and the rational numbers as constant functions and that is closed under addition, multiplication, and composition. If is an expression in , then let be the function denoted by .Then the integration problem for is the problem of deciding, given in , whether there is a function in so that (Richardson 1968).

Frobenius equation

The Frobenius equation is the Diophantine equationwhere the are positive integers, is an integer, and the solutions are nonnegative integers. Solution of the Frobenius equation is implemented using FrobeniusSolve[a1, ..., an, b].The largest value for which the Frobenius equation has no solution is known as the Frobenius number.

Postage stamp problem

Consider a set of positive integer-denomination postage stamps sorted such that . Suppose they are to be used on an envelope with room for no more than stamps. The postage stamp problem then consists of determining the smallest integer which cannot be represented by a linear combination with and .Without the latter restriction, this problem is known as the Frobenius problem or Frobenius postage stamp problem.The number of consecutive possible postage amounts is given by(1)where is called an -range.Exact solutions exist for arbitrary for and 3. The solution is(2)for . It is also known that(3)(Stöhr 1955, Guy 1994), where is the floor function, the first few values of which are 2, 4, 7, 10, 14, 18, 23, 28, 34, 40, ... (OEIS A014616; Guy 1994, p. 123).Hofmeister (1968, 1983) showed that for ,(4)where and are functions of (mod 9), and Mossige (1981, 1987) showed that(5)(Guy 1994, p. 123).Shallit (2002) proved that the (local) postage..

Lattice reduction

The process of finding a reduced set of basis vectors for a given lattice having certain special properties. Lattice reduction algorithms are used in a number of modern number theoretical applications, including in the discovery of a spigot algorithm for pi. Although determining the shortest basis is possibly an NP-complete problem, algorithms such as the LLL algorithm can find a short basis in polynomial time with guaranteed worst-case performance.The LLL algorithm of lattice reduction is implemented in the Wolfram Language using the function LatticeReduce. RootApproximant[x, n] also calls this routine in order to find a algebraic number of degree at most such that is an approximate zero of the number.When used to find integer relations, a typical input to the algorithm consists of an augmented identity matrix with the entries in the last column consisting of the elements (multiplied by a large positive constant to penalize vectors that..

Lll algorithm

A lattice reduction algorithm, named after discoverers Lenstra, Lenstra, and Lovasz (1982), that produces a lattice basis of "short" vectors. It was noticed by Lenstra et al. (1982) that the algorithm could be used to obtain factors of univariate polynomials, which amounts to the determination of integer relations. However, this application of the algorithm, which later came to be one of its primary applications, was not stressed in the original paper.For a complexity analysis of the LLL algorithm, see Storjohann (1996).The Wolfram Language command LatticeReduce[matrix] implements the LLL algorithm to perform lattice reduction. The Wolfram Language's implementation requires the input to consist of rational numbers, so Rationalize may need to be called first.More recently, other algorithms such as PSLQ, which can be significant faster than LLL, have been developed for finding integer relations. PSLQ achieves its performance..

Pslq algorithm

An algorithm which can be used to find integer relations between real numbers , ..., such thatwith not all . Although the algorithm operates by manipulating a lattice, it does not reduce it to a short vector basis, and is therefore not a lattice reduction algorithm. PSLQ is based on a partial sum of squares scheme (like the PSOS algorithm) implemented using QR decomposition. It was developed by Ferguson and Bailey (1992). A much simplified version of the algorithm was subsequently developed by Ferguson et al. (1999), which also extends the algorithm to complex numbers and quaternions. Ferguson et al. (1999) also demonstrated that PSLQ is distinct from the HJLS algorithm.The PSLQ algorithm terminates after a number of iterations bounded by a polynomial in and uses a numerically stable matrix reduction procedure (Ferguson and Bailey 1992). PSLQ tends to be faster than the Ferguson-Forcade algorithm and LLL algorithm because of clever techniques..

Integer relation

A set of real numbers , ..., is said to possess an integer relation if there exist integers such thatwith not all . For historical reasons, integer relation algorithms are sometimes called generalized Euclidean algorithms or multidimensional continued fraction algorithms.An interesting example of such a relation is the 17-vector (1, , , ..., ) with , which has an integer relation (1, 0, 0, 0, , 0, 0, 0, , 0, 0, 0, , 0, 0, 0, 1), i.e.,This is a special case of finding the polynomial of degree satisfied by .Integer relations can be found in the Wolfram Language using FindIntegerNullVector[x1, x2, ...].Integer relation algorithms can be used to solve subset sum problems, as well as to determine if a given numerical constant is equal to a root of a univariate polynomial of degree or less (Bailey and Ferguson 1989, Ferguson and Bailey 1992).One of the simplest cases of an integer relation between two numbers is the one inherent in the definition of the greatest..

Subset sum problem

There are two problems commonly known as the subset sum problem.The first ("given sum problem") is the problem of finding what subset of a list of integers has a given sum, which is an integer relation problem where the relation coefficients are 0 or 1.The ("same sum problem") is the problem of finding a set of distinct positive real numbers with as large a collection as possible of subsets with the same sum (Proctor 1982).The same sum problem was solved by Stanley (1980) using the tools of algebraic geometry, with the answer given for numbers by the first positive integers: . Proctor (1982) gave the first elementary proof of this result. The maximal numbers of subsets of having the same sum for , 2, ... are 1, 1, 2, 2, 3, 5, 8, 14, 23, ... (OEIS A025591). Similarly, the numbers of different subset sums for , 2, ... are 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, ... (OEIS A000124). For example, for , the subsets of are(1)(2)(3)(4)(5)(6)(7)(8)so..

Subscribe to our updates
79 345 subscribers already with us
Math Subcategories
Check the price
for your project