{
  "id": "enwiki-001250450504",
  "slug": "abramov-s-algorithm",
  "title": "Abramov's algorithm",
  "qid": "",
  "lead": "In mathematics, particularly in computer algebra, Abramov's algorithm computes all rational solutions of a linear recurrence equation with polynomial coefficients. The algorithm was published by Sergei A. Abramov in 1989.",
  "body": "In mathematics, particularly in computer algebra, Abramov's algorithm computes all rational solutions of a linear recurrence equation with polynomial coefficients. The algorithm was published by Sergei A. Abramov in 1989. The main concept in Abramov's algorithm is a universal denominator. Let \\mathbb{K} be a field of characteristic zero. The dispersion \\operatorname{dis} (p,q) of two polynomials p, q \\in \\mathbb{K}[n] is defined as \\operatorname{dis} (p,q) =\\max \\{ k \\in \\N \\, : \\, \\deg (\\gcd (p(n), q(n+k) )) \\geq 1 \\} \\cup \\{ -1 \\}, where \\N denotes the set of non-negative integers. Therefore the dispersion is the maximum k \\in \\N such that the polynomial p and the k -times shifted polynomial q have a common factor. It is -1 if such a k does not exist. The dispersion can be computed as the largest non-negative integer root of the resultant \\operatorname{res}_n (p(n), q(n+k) ) \\in \\mathbb{K}[k] . Let \\sum_{k=0}^r p_k(n) \\, y (n+k) = f(n) be a recurrence equation of order r with polynomial coefficients p_k \\in \\mathbb{K} [n] , polynomial right-hand side f \\in \\mathbb{K}[n] and rational sequence solution y (n) \\in \\mathbb{K}(n) . It is possible to write y (n) = p(n)/q(n) for two relatively prime polynomials p, q \\in \\mathbb{K}[n] . Let D=\\operatorname{dis} (p_r(n-r), p_0 (n) ) and u(n) = \\gcd ([p_0 (n+D)]^{\\underline{D+1}}, [p_r (n-r)]^{\\underline{D+1}}) where [p(n)]^{\\underline{k}}=p(n)p(n-1)\\cdots p(n-k+1) denotes the falling factorial of a function. Then q(n) divides u(n) . So the polynomial u(n) can be used as a denominator for all rational solutions y(n) and hence it is called a universal denominator. Let again \\sum_{k=0}^r p_k(n) \\, y (n+k) = f(n) be a recurrence equation with polynomial coefficients and u(n) a universal denominator. After substituting y (n) = z(n)/u(n) for an unknown polynomial z(n) \\in \\mathbb{K} [n] and setting \\ell(n) = \\operatorname{lcm}(u(n), \\dots, u(n+r)) the recurrence equation is equivalent to \\sum_{k=0}^r p_k (n) \\frac{z(n+k)}{u(n+k)} \\ell(n) = f(n) \\ell(n). As the u(n+k) cancel this is a linear recurrence equation with polynomial coefficients which can be solved for an unknown polynomial solution z(n) . There are algorithms to find polynomial solutions. The solutions for z(n) can then be used again to compute the rational solutions y(n) = z(n)/u(n) . algorithm rational_solutions is input: Linear recurrence equation \\sum_{k=0}^r p_k(n) \\, y (n+k) = f(n), p_k, f \\in \\mathbb{K}[n], p_0, p_r \\neq 0 . output: The general rational solution y if there are any solutions, otherwise false. D = \\operatorname{disp} (p_r(n-r), p_0 (n) ) u(n) = \\gcd ([p_0 (n+D)]^{\\underline{D+1}}, [p_r (n-r)]^{\\underline{D+1}}) \\ell(n) = \\operatorname{lcm}(u(n), \\dots, u(n+r)) Solve \\sum_{k=0}^r p_k (n) \\frac{z(n+k)}{u(n+k)} \\ell(n) = f(n) \\ell(n) for general polynomial solution z(n) if solution z(n) exists then return general solution y (n) = z(n)/u(n) else return false end if The homogeneous recurrence equation of order 1 (n-1) \\, y(n) + (-n-1) \\, y(n+1) = 0 over \\Q has a rational solution. It can be computed by considering the dispersion D = \\operatorname{dis} (p_1 (n-1), p_0 (n) ) = \\operatorname{disp} (-n,n-1) = 1. This yields the following universal denominator: u(n) = \\gcd ([p_0 (n+1)]^{\\underline{2}}, [p_r (n-1)]^{\\underline{2}}) = (n-1)n and \\ell(n) = \\operatorname{lcm} (u(n), u(n+1) ) = (n-1)n(n+1). Multiplying the original recurrence equation with \\ell(n) and substituting y(n) = z(n)/u(n) leads to (n-1)(n+1)\\, z(n) + (-n-1) (n-1) \\, z(n+1) = 0. This equation has the polynomial solution z(n) = c for an arbitrary constant c \\in \\Q . Using y(n) = z(n) / u(n) the general rational solution is y(n) = \\frac{c}{(n-1)n} for arbitrary c \\in \\Q .",
  "categories": [
    "26870223"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1250450504",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1728561451.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001250450504",
    "type": "webpage",
    "title": "Abramov's algorithm",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/abramov-s-algorithm",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001250450504",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1250450504",
    "note": "Immutable snapshot enwiki-001250450504"
  }
}