View source for Lill's method

{{short description|Graphical method for the real roots of a polynomial}}
[[File:Lill_method_quartic_example.svg|thumb|Finding roots −2, −1 (repeated root), and −1/3 of the quartic 3''x''<sup>4</sup>+13''x''<sup>3</sup>+19''x''<sup>2</sup>+11''x''+2 using Lill's method. Black segments are labeled with their lengths (coefficients in the equation), while each colored line with initial slope ''m'' and the same endpoint corresponds to a real root.]]
In [[mathematics]], '''Lill's method''' is a visual method of finding the [[real number|real]] [[zero of a function|roots]] of a univariate [[polynomial]] of any [[degree of a polynomial|degree]].<ref>{{cite book |title=Uncommon Mathematical Excursions: Polynomia and Related Realms |url=https://archive.org/details/uncommonmathemat00kalm_338 |url-access=limited |author=Dan Kalman |publisher=AMS |year=2009 |isbn=978-0-88385-341-2 |pages=[https://archive.org/details/uncommonmathemat00kalm_338/page/n29 13]–22}}</ref> It was developed by Austrian engineer [[Eduard Lill]] in 1867.<ref>{{cite journal|title=Résolution graphique des équations numériques de tous degrés à une seule inconnue, et description d'un instrument inventé dans ce but |author= M. E. Lill |journal=[[Nouvelles Annales de Mathématiques]] |series=2 |volume=6 |year=1867 |pages=359–362|url=http://archive.numdam.org/article/NAM_1867_2_6__359_0.pdf}}</ref> A later paper by Lill dealt with the problem of [[complex numbers|complex]] roots.<ref name=":1">{{cite journal|title=Résolution graphique des équations algébriques qui ont des racines imaginaires |author= M. E. Lill|journal=[[Nouvelles Annales de Mathématiques]] |series=2 |volume=7 |year=1868 |pages=363–367|url=http://archive.numdam.org/article/NAM_1868_2_7__363_1.pdf}} </ref>

Lill's method involves drawing a path of straight line segments making [[Right angle|right angles]], with lengths equal to the coefficients of the polynomial. The roots of the polynomial can then be found as the [[Slope|slopes]] of other right-angle paths, also connecting the start to the terminus, but with vertices on the lines of the first path.

==Description of the method==
[[File:LillsMethod.svg|thumb|right|250px|Finding roots −1/2, −1/{{radic|2}}, and 1/{{radic|2}} of the cubic {{Math|4''x''<sup>3</sup> + 2''x''<sup>2</sup> &minus; 2''x'' &minus; 1}}, showing how negative coefficients and extended segments are handled. Each number shown on a colored line is the negative of its slope and hence a real root of the polynomial.]]

To employ the method, a diagram is drawn starting at the origin. A line segment is drawn rightwards by the magnitude of the leading coefficient, so that with a negative coefficient, the segment will end left of the origin. From the end of the first segment, another segment is drawn upwards by the magnitude of the second coefficient, then left by the magnitude of the third, then down by the magnitude of the fourth, and so on. The sequence of directions (not turns) is always rightward, upward, leftward, downward, then repeating itself. Thus, each turn is counterclockwise. The process continues for every coefficient of the polynomial, including zeros, with negative coefficients "walking backwards." The final point reached, at the end of the segment corresponding to the equation's constant term, is the terminus.

A line is then launched from the origin at some angle {{mvar|θ}}, reflected off of each line segment at a right angle (not necessarily the "natural" angle of reflection), and [[Refraction|refracted]] at a right angle through the line through each segment (including a line for the zero coefficients) when the angled path does not hit the line segment on that line.<ref name=":0">{{cite web|last=Bradford|first=Phillips Verner|url=http://www.concentric.net/~pvb/ALG/rightpaths.html|title=Visualizing solutions to n-th degree algebraic equations using right-angle geometric paths|publisher=www.concentric.net|accessdate=3 February 2012|url-status=dead|archiveurl=https://web.archive.org/web/20100502013959/http://www.concentric.net/~pvb/ALG/rightpaths.html|archivedate=2 May 2010}}</ref> The vertical and horizontal lines are reflected off or refracted through in the following sequence: the line containing the segment corresponding to the coefficient of {{Math|''x''<sup>''n''&minus;1</sup>}}, then of {{Math|''x''<sup>''n''&minus;2</sup>}} etc. Choosing {{mvar|θ}} so that the path lands on the terminus, {{Math|&minus;tan(''&theta;'')}} is a root of this polynomial. For every real zero of the polynomial, there will be one unique initial angle and path that will land on the terminus. A quadratic with two real roots, for example, will have exactly two angles that satisfy the above conditions.

For complex roots, one must also find a series of [[Similarity (geometry)|similar]] triangles, but with the vertices of the root path displaced from the polynomial path by a distance equal to the imaginary part of the root. In this case, the root path will not be rectangular.<ref>{{Cite journal|last=Tabachnikov|first=Serge|date=2017-03-01|title=Polynomials as Polygons|url=http://www.personal.psu.edu/sot2/prints/Polynomials.pdf|journal=The Mathematical Intelligencer|language=en|volume=39|issue=1|pages=41–43|doi=10.1007/s00283-016-9681-y|s2cid=126072703|issn=1866-7414}}</ref><ref name=":1" />

=== Explanation ===
The construction in effect evaluates the polynomial according to [[Horner's method]]. For the polynomial <math>a_n x^n+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+ \cdots</math>, the values of <math>a_n x</math>, <math>(a_n x+a_{n-1})x</math>, <math>((a_n x+a_{n-1})x+a_{n-2})x</math>, ... are successively generated as distances between the vertices of the polynomial and root paths. For a root of the polynomial, the final value is zero, so the last vertex coincides with the polynomial path terminus.  

=== Additional properties ===
A solution line giving a root is similar to the Lill's construction for the polynomial with that root removed, because the visual construction is analogous to the [[synthetic division]] of the polynomial by a linear (root) [[Monic polynomial|monic]] ([[Ruffini's rule]]).

From the symmetry of the diagram, it can easily be seen that the roots of the [[Reciprocal polynomial|reversed polynomial]] are the [[Multiplicative inverse|reciprocals]] of the original roots. 

The construction can also be done using clockwise turns instead of counterclockwise turns. When a path is interpreted using the other convention, it corresponds to the mirrored polynomial (every odd coefficient's sign is changed), and the roots are negated.

When the right-angle path is traversed in the other direction but with the same direction convention, it corresponds to the reversed mirrored polynomial, and the roots are the negative reciprocals of the original roots.<ref name=":0" />

=== Finding quadratic roots using Thales's theorem ===
[[File:Lill_method_quadratic_example.svg|thumb|left|upright=0.5|Finding roots of {{Math|3''x''<sup>2</sup> + 5''x'' &minus; 2}}]]
Lill's method can be used with [[Thales's theorem]] to find the real roots of a quadratic polynomial.

In this example with {{Math|3''x''<sup>2</sup> + 5''x'' &minus; 2}}, the polynomial's line segments are first drawn in black, as above. A circle is drawn with the straight line segment joining the start and end points forming a diameter.

According to Thales's theorem, the triangle containing these points and any other point on the circle is a [[right triangle]]. Intersects of this circle with the middle segment of Lill's method, extended if needed, thus define the two angled paths in Lill's method, colored blue and red.

The negative of the gradients of their first segments, {{Mvar|m}}, yield the real roots {{Math|1/3}} and {{Math|&minus;2}}.{{Clear|left}}

=== Finding roots using paper folding ===
[[File:Lill_method_folding_example.svg|thumb|250px|Find roots of {{Math|3''x''<sup>3</sup> + 2''x''<sup>2</sup> &minus; 7''x'' + 2}}]]
In 1936, [[Margherita Piazzola Beloch]] showed how Lill's method could be adapted to solve cubic equations using [[paper folding]].<ref>{{cite journal |title=Solving Cubics With Creases: The Work of Beloch and Lill |author=Thomas C. Hull|url=http://mars.wne.edu/~thull/papers/amer.math.monthly.118.04.307-hull.pdf|journal=American Mathematical Monthly |date=April 2011|volume=118|issue=4|pages=307–315|doi=10.4169/amer.math.monthly.118.04.307|s2cid=2540978}}</ref> If simultaneous folds are allowed, then any {{Mvar|n}}th-degree equation with a real root can be solved using {{Math|''n'' &minus; 2}} simultaneous folds.<ref>{{cite journal |title=One-, Two-, and Multi-Fold Origami Axioms|url=http://www.math.sjsu.edu/~alperin/AlperinLang.pdf |author1=Roger C. Alperin |author2=Robert J. Lang |journal=4OSME|publisher=A K Peters |year=2009}}</ref>

In this example with {{Math|3''x''<sup>3</sup> + 2''x''<sup>2</sup> &minus; 7''x'' + 2}}, the polynomial's line segments are first drawn on a sheet of paper (black). Lines passing through reflections of the start and end points in the second and third segments, respectively (faint circle and square), and parallel to them (grey lines), are drawn.

For each root, the paper is folded until the start point (black circle) and end point (black square) are reflected onto these lines. The axis of reflection (dash-dot line) defines the angled path corresponding to the root (blue, purple, and red). The negative of the gradients of their first segments, ''{{Mvar|m}}'', yield the real roots {{Math|1/3}}, {{Math|1}}, and {{Math|&minus;2}}.

== See also ==
*[[Carlyle circle]], which is based on a slightly modified version of Lill's method for a normed quadratic.

==References==
{{Reflist}}

==External links==
{{commonscat}}
* [http://dankalman.net/ume/lill/ Animation for Lill's Method]
* [https://www.youtube.com/watch?v=IUC-8P0zXe8 Mathologer video: "Solving equations by shooting turtles with lasers"]

[[Category:1867 introductions]]
[[Category:1867 in science]]
[[Category:Geometry]]
[[Category:Paper folding]]
[[Category:Polynomials]]

{{Mathematics of paper folding}}