text:
Entire function

In complex analysis, an entire function, also called an integral function, is a complex-valued function that is holomorphic on the whole complex plane. Typical examples of entire functions are polynomials and the exponential function, and any finite sums, products and compositions of these, such as the trigonometric functions sine and cosine and their hyperbolic counterparts sinh and cosh, as well as derivatives and integrals of entire functions such as the error function. If an entire function $$f(z)$$ has a root at $$w$$, then $$f(z)/(z-w)$$, taking the limit value at $$w$$, is an entire function. On the other hand, the natural logarithm, the reciprocal function, and the square root are all not entire functions, nor can they be continued analytically to an entire function.

A transcendental entire function is an entire function that is not a polynomial.

Just as meromorphic functions can be viewed as a generalization of rational fractions, entire functions can be viewed as a generalization of polynomials. In particular, if for meromorphic functions one can generalize the factorization into simple fractions (the Mittag-Leffler theorem on the decomposition of a meromorphic function), then for entire functions there is a generalization of the factorization — the Weierstrass theorem on entire functions.

Properties
Every entire function $$\ f(z)\ $$ can be represented as a single power series $$\ f(z) = \sum_{n=0}^\infty a_n z^n\ $$ that converges everywhere in the complex plane, hence uniformly on compact sets. The radius of convergence is infinite, which implies that $$\ \lim_{n\to\infty} |a_n|^{\frac{1}{n}} = 0\ $$ or, equivalently, $$\ \lim_{n\to\infty} \frac{\ln|a_n|}n = -\infty ~.$$ Any power series satisfying this criterion will represent an entire function.

If (and only if) the coefficients of the power series are all real then the function evidently takes real values for real arguments, and the value of the function at the complex conjugate of $$\ z\ $$ will be the complex conjugate of the value at $$\ z ~.$$ Such functions are sometimes called self-conjugate (the conjugate function, $$\ F^*(z)\ ,$$ being given by $\ \bar F(\bar z)\ $).

If the real part of an entire function is known in a neighborhood of a point then both the real and imaginary parts are known for the whole complex plane, up to an imaginary constant. For instance, if the real part is known in a neighborhood of zero, then we can find the coefficients for $$n>0$$ from the following derivatives with respect to a real variable $$\ r\ $$:

$$\begin{align} \operatorname\mathcal{R_e} \left\{\ a_n\ \right\} &= \frac{1}{n!} \frac{d^n}{dr^n}\ \operatorname\mathcal{R_e} \left\{\ f(r)\ \right\} && \quad \mathrm{ at } \quad r = 0 \\ \operatorname\mathcal{I_m}\left\{\ a_n\ \right\} &= \frac{1}{n!} \frac{d^n}{dr^n}\ \operatorname\mathcal{R_e} \left\{\ f\left( r\ e^{-\frac{i\pi}{2n}} \right)\ \right\} && \quad \mathrm{ at } \quad r = 0 \end{align}$$

(Likewise, if the imaginary part is known in a neighborhood then the function is determined up to a real constant.) In fact, if the real part is known just on an arc of a circle, then the function is determined up to an imaginary constant.} Note however that an entire function is not determined by its real part on all curves. In particular, if the real part is given on any curve in the complex plane where the real part of some other entire function is zero, then any multiple of that function can be added to the function we are trying to determine. For example, if the curve where the real part is known is the real line, then we can add $$\ i\ $$ times any self-conjugate function. If the curve forms a loop, then it is determined by the real part of the function on the loop since the only functions whose real part is zero on the curve are those that are everywhere equal to some imaginary number.

The Weierstrass factorization theorem asserts that any entire function can be represented by a product involving its zeroes (or "roots").

The entire functions on the complex plane form an integral domain (in fact a Prüfer domain). They also form a commutative unital associative algebra over the complex numbers.

Liouville's theorem states that any bounded entire function must be constant.

As a consequence of Liouville's theorem, any function that is entire on the whole Riemann sphere is constant. Thus any non-constant entire function must have a singularity at the complex point at infinity, either a pole for a polynomial or an essential singularity for a transcendental entire function. Specifically, by the Casorati–Weierstrass theorem, for any transcendental entire function $$\ f\ $$ and any complex $$\ w\ $$ there is a sequence $$\ (z_m)_{m\in\N}\ $$ such that

 * $$\ \lim_{m\to\infty} |z_m| = \infty, \qquad \text{and} \qquad \lim_{m\to\infty} f(z_m) = w ~.$$

Picard's little theorem is a much stronger result: Any non-constant entire function takes on every complex number as value, possibly with a single exception. When an exception exists, it is called a lacunary value of the function. The possibility of a lacunary value is illustrated by the exponential function, which never takes on the value $0$. One can take a suitable branch of the logarithm of an entire function that never hits $0$, so that this will also be an entire function (according to the Weierstrass factorization theorem). The logarithm hits every complex number except possibly one number, which implies that the first function will hit any value other than 0 an infinite number of times. Similarly, a non-constant, entire function that does not hit a particular value will hit every other value an infinite number of times.

Liouville's theorem is a special case of the following statement:

$$

Growth
Entire functions may grow as fast as any increasing function: for any increasing function $$g:[0,\infty)\to[0,\infty)$$ there exists an entire function $$f$$ such that $$f(x)>g(|x|)$$ for all real $$x$$. Such a function $$f$$ may be easily found of the form:

$$f(z)=c+\sum_{k=1}^{\infty}\left(\frac{z}{k}\right)^{n_k}$$

for a constant $$c$$ and a strictly increasing sequence of positive integers $$n_k$$. Any such sequence defines an entire function $$f(z)$$, and if the powers are chosen appropriately we may satisfy the inequality $$f(x)>g(|x|)$$ for all real $$x$$. (For instance, it certainly holds if one chooses $$c:=g(2)$$ and, for any integer $$k \ge 1$$ one chooses an even exponent $$ n_k $$ such that $$\left(\frac{k+1}{k}\right)^{n_k} \ge g(k+2)$$).

Order and type
The order (at infinity) of an entire function $$f(z)$$ is defined using the limit superior as:

$$\rho = \limsup_{r\to\infty}\frac{\ln \left (\ln\| f \|_{\infty, B_r} \right ) }{\ln r},$$

where $$B_r$$ is the disk of radius $$r$$ and $$\|f \|_{\infty, B_r}$$ denotes the supremum norm of $$f(z)$$ on $$B_r$$. The order is a non-negative real number or infinity (except when $$f(z) = 0$$ for all $$z$$. In other words, the order of $$f(z)$$ is the infimum of all $$m$$ such that:

$$f(z) = O \left (\exp \left (|z|^m \right ) \right ), \quad \text{as } z \to \infty.$$

The example of $$f(z) = \exp(2z^2)$$ shows that this does not mean $$f(z)=O(\exp(|z|^m))$$ if $$f(z)$$ is of order $$m$$.

If $$0<\rho < \infty,$$ one can also define the type:

$$\sigma=\limsup_{r\to\infty}\frac{\ln \| f\|_{\infty, B_r}} {r^\rho}.$$

If the order is 1 and the type is $$\sigma$$, the function is said to be "of exponential type $$\sigma$$". If it is of order less than 1 it is said to be of exponential type 0.

If $$ f(z)=\sum_{n=0}^\infty a_n z^n,$$ then the order and type can be found by the formulas $$\begin{align} \rho &=\limsup_{n\to\infty} \frac{n\ln n}{-\ln|a_n|} \\[6pt] (e\rho\sigma)^{\frac{1}{\rho}} &= \limsup_{n\to\infty} n^{\frac{1}{\rho}} |a_n|^{\frac{1}{n}} \end{align}$$

Let $$f^{(n)}$$ denote the $$n$$-th derivative of $$f$$, then we may restate these formulas in terms of the derivatives at any arbitrary point $$z_0$$:

$$\begin{align} \rho &=\limsup_{n\to\infty}\frac{n\ln n}{n\ln n-\ln|f^{(n)}(z_0)|}=\left(1-\limsup_{n\to\infty}\frac{\ln|f^{(n)}(z_0)|}{n\ln n}\right)^{-1} \\[6pt] (\rho\sigma)^{\frac{1}{\rho}} &=e^{1-\frac{1}{\rho}} \limsup_{n\to\infty}\frac{|f^{(n)}(z_0)|^{\frac{1}{n}}}{n^{1-\frac{1}{\rho}}} \end{align}$$

The type may be infinite, as in the case of the reciprocal gamma function, or zero (see example below under ).

Another way to find out the order and type is Matsaev's theorem.

Examples
Here are some examples of functions of various orders:

Order ρ
For arbitrary positive numbers $$\rho$$ and $$\sigma$$ one can construct an example of an entire function of order $$\rho$$ and type $$\sigma$$ using:

$$f(z)=\sum_{n=1}^\infty \left (\frac{e\rho\sigma}{n} \right )^{\frac{n}{\rho}} z^n$$

Order 0

 * Non-zero polynomials
 * $$\sum_{n=0}^\infty 2^{-n^2} z^n$$

Order 1/4
$$f(\sqrt[4]z)$$ where $$f(u)=\cos(u)+\cosh(u)$$

Order 1/3
$$f(\sqrt[3]z)$$ where $$f(u)=e^u+e^{\omega u}+e^{\omega^2 u} = e^u+2e^{-\frac{u}{2}}\cos \left (\frac{\sqrt 3u}{2} \right ), \quad \text{with } \omega \text{ a complex cube root of 1}.$$

Order 1/2
$$\cos \left (a\sqrt z \right )$$ with $$a\neq 0$$ (for which the type is given by $$\sigma=|a|$$)

Order 1

 * $$\exp(az)$$ with $$a\neq 0$$ ($$\sigma=|a|$$)
 * $$\sin(z)$$
 * $$\cosh(z)$$
 * the reciprocal gamma function $$1/\Gamma(z)$$ ($$\sigma$$ is infinite)
 * $$\sum_{n=2}^\infty \frac{z^n}{(n\ln n)^n}. \quad (\sigma=0)$$

Order 3/2

 * Airy function $$Ai(z)$$

Order 2

 * $$\exp(az^2)$$ with $$a\neq 0$$ ($$\sigma=|a|$$)
 * The Barnes G-function ($$\sigma$$ is infinite).

Order infinity

 * $$\exp(\exp(z))$$

Genus
Entire functions of finite order have Hadamard's canonical representation (Hadamard factorization theorem):

$$f(z)=z^me^{P(z)}\prod_{n=1}^\infty\left(1-\frac{z}{z_n}\right)\exp\left(\frac{z}{z_n}+\cdots+\frac{1}{p} \left(\frac{z}{z_n}\right)^p\right),$$

where $$z_k$$ are those roots of $$f$$ that are not zero ($$z_k \neq 0$$), $$m$$ is the order of the zero of $$f$$ at $$z = 0$$ (the case $$m = 0$$ being taken to mean $$f(0) \neq 0$$), $$P$$ a polynomial (whose degree we shall call $$q$$), and $$p$$ is the smallest non-negative integer such that the series

$$\sum_{n=1}^\infty\frac{1}{|z_n|^{p+1}}$$

converges. The non-negative integer $$g=\max\{p, q\}$$ is called the genus of the entire function $$f$$.

If the order $$\rho$$ is not an integer, then $$g = [ \rho ]$$ is the integer part of $$\rho$$. If the order is a positive integer, then there are two possibilities: $$g = \rho-1$$ or $$g = \rho $$.

For example, $$\sin$$, $$\cos$$ and $$\exp$$ are entire functions of genus $$g = \rho = 1$$.

Other examples
According to J. E. Littlewood, the Weierstrass sigma function is a 'typical' entire function. This statement can be made precise in the theory of random entire functions: the asymptotic behavior of almost all entire functions is similar to that of the sigma function. Other examples include the Fresnel integrals, the Jacobi theta function, and the reciprocal Gamma function. The exponential function and the error function are special cases of the Mittag-Leffler function. According to the fundamental theorem of Paley and Wiener, Fourier transforms of functions (or distributions) with bounded support are entire functions of order $$1$$ and finite type.

Other examples are solutions of linear differential equations with polynomial coefficients. If the coefficient at the highest derivative is constant, then all solutions of such equations are entire functions. For example, the exponential function, sine, cosine, Airy functions and Parabolic cylinder functions arise in this way. The class of entire functions is closed with respect to compositions. This makes it possible to study dynamics of entire functions.

An entire function of the square root of a complex number is entire if the original function is even, for example $$\cos(\sqrt{z})$$.

If a sequence of polynomials all of whose roots are real converges in a neighborhood of the origin to a limit which is not identically equal to zero, then this limit is an entire function. Such entire functions form the Laguerre–Pólya class, which can also be characterized in terms of the Hadamard product, namely, $$f$$ belongs to this class if and only if in the Hadamard representation all $$z_n$$ are real, $$\rho\leq 1$$, and $$P(z)=a+bz+cz^2$$, where $$b$$ and $$c$$ are real, and $$c\leq 0$$. For example, the sequence of polynomials

$$\left (1-\frac{(z-d)^2}{n} \right )^n$$

converges, as $$n$$ increases, to $$\exp(-(z-d)^2)$$. The polynomials

$$ \frac{1}{2}\left ( \left (1+\frac{iz}{n} \right )^n+ \left (1-\frac{iz}{n} \right )^n \right )$$

have all real roots, and converge to $$\cos(z)$$. The polynomials

$$ \prod_{m=1}^n \left(1-\frac{z^2}{\left ( \left (m-\frac{1}{2} \right )\pi \right )^2}\right)$$

also converge to $$\cos(z)$$, showing the buildup of the Hadamard product for cosine.

title: Entire function


text:
Essay

An essay is, generally, a piece of writing that gives the author's own argument, but the definition is vague, overlapping with those of a letter, a paper, an article, a pamphlet, and a short story. Essays have been sub-classified as formal and informal: formal essays are characterized by "serious purpose, dignity, logical organization, length," whereas the informal essay is characterized by "the personal element (self-revelation, individual tastes and experiences, confidential manner), humor, graceful style, rambling structure, unconventionality or novelty of theme," etc.

Essays are commonly used as literary criticism, political manifestos, learned arguments, observations of daily life, recollections, and reflections of the author. Almost all modern essays are written in prose, but works in verse have been dubbed essays (e.g., Alexander Pope's An Essay on Criticism and An Essay on Man). While brevity usually defines an essay, voluminous works like John Locke's An Essay Concerning Human Understanding and Thomas Malthus's An Essay on the Principle of Population are counterexamples.

In some countries (e.g., the United States and Canada), essays have become a major part of formal education. Secondary students are taught structured essay formats to improve their writing skills; admission essays are often used by universities in selecting applicants, and in the humanities and social sciences essays are often used as a way of assessing the performance of students during final exams.

The concept of an "essay" has been extended to other media beyond writing. A film essay is a movie that often incorporates documentary filmmaking styles and focuses more on the evolution of a theme or idea. A photographic essay covers a topic with a linked series of photographs that may have accompanying text or captions.

Definitions
The word essay derives from the French infinitive essayer, "to try" or "to attempt". In English essay first meant "a trial" or "an attempt", and this is still an alternative meaning. The Frenchman Michel de Montaigne (1533–1592) was the first author to describe his work as essays; he used the term to characterize these as "attempts" to put his thoughts into writing.

Subsequently, essay has been defined in a variety of ways. One definition is a "prose composition with a focused subject of discussion" or a "long, systematic discourse". It is difficult to define the genre into which essays fall. Aldous Huxley, a leading essayist, gives guidance on the subject. He notes that "the essay is a literary device for saying almost everything about almost anything", and adds that "by tradition, almost by definition, the essay is a short piece". Furthermore, Huxley argues that "essays belong to a literary species whose extreme variability can be studied most effectively within a three-poled frame of reference". These three poles (or worlds in which the essay may exist) are: Huxley adds that the most satisfying essays "...make the best not of one, not of two, but of all the three worlds in which it is possible for the essay to exist."
 * The personal and the autobiographical: The essayists that feel most comfortable in this pole "write fragments of reflective autobiography and look at the world through the keyhole of anecdote and description".
 * The objective, the factual, and the concrete particular: The essayists that write from this pole "do not speak directly of themselves, but turn their attention outward to some literary or scientific or political theme. Their art consists of setting forth, passing judgment upon, and drawing general conclusions from the relevant data".
 * The abstract-universal: In this pole "we find those essayists who do their work in the world of high abstractions", who are never personal and who seldom mention the particular facts of experience.

Montaigne
Montaigne's "attempts" grew out of his commonplacing. Inspired in particular by the works of Plutarch, a translation of whose Œuvres Morales (Moral works) into French had just been published by Jacques Amyot, Montaigne began to compose his essays in 1572; the first edition, entitled Essais, was published in two volumes in 1580. For the rest of his life, he continued revising previously published essays and composing new ones. A third volume was published posthumously; together, their over 100 examples are widely regarded as the predecessor of the modern essay.

Europe
While Montaigne's philosophy was admired and copied in France, none of his most immediate disciples tried to write essays. But Montaigne, who liked to fancy that his family (the Eyquem line) was of English extraction, had spoken of the English people as his "cousins", and he was early read in England, notably by Francis Bacon.

Bacon's essays, published in book form in 1597 (only five years after the death of Montaigne, containing the first ten of his essays), 1612, and 1625, were the first works in English that described themselves as essays. Ben Jonson first used the word essayist in 1609, according to the Oxford English Dictionary. Other English essayists included Sir William Cornwallis, who published essays in 1600 and 1617 that were popular at the time, Robert Burton (1577–1641) and Sir Thomas Browne (1605–1682). In Italy, Baldassare Castiglione wrote about courtly manners in his essay Il Cortigiano. In the 17th century, the Spanish Jesuit Baltasar Gracián wrote about the theme of wisdom.

In England, during the Age of Enlightenment, essays were a favored tool of polemicists who aimed at convincing readers of their position; they also featured heavily in the rise of periodical literature, as seen in the works of Joseph Addison, Richard Steele and Samuel Johnson. Addison and Steele used the journal Tatler (founded in 1709 by Steele) and its successors as storehouses of their work, and they became the most celebrated eighteenth-century essayists in England. Johnson's essays appear during the 1750s in various similar publications. As a result of the focus on journals, the term also acquired a meaning synonymous with "article", although the content may not the strict definition. On the other hand, Locke's An Essay Concerning Human Understanding is not an essay at all, or cluster of essays, in the technical sense, but still it refers to the experimental and tentative nature of the inquiry which the philosopher was undertaking.

In the 18th and 19th centuries, Edmund Burke and Samuel Taylor Coleridge wrote essays for the general public. The early 19th century, in particular, saw a proliferation of great essayists in English—William Hazlitt, Charles Lamb, Leigh Hunt and Thomas De Quincey all penned numerous essays on diverse subjects, reviving the earlier graceful style. Thomas Carlyle's essays were highly influential, and one of his readers, Ralph Waldo Emerson, became a prominent essayist himself. Later in the century, Robert Louis Stevenson also raised the form's literary level. In the 20th century, a number of essayists, such as T.S. Eliot, tried to explain the new movements in art and culture by using essays. Virginia Woolf, Edmund Wilson, and Charles du Bos wrote literary criticism essays.

In France, several writers produced longer works with the title of essai that were not true examples of the form. However, by the mid-19th century, the Causeries du lundi, newspaper columns by the critic Sainte-Beuve, are literary essays in the original sense. Other French writers followed suit, including Théophile Gautier, Anatole France, Jules Lemaître and Émile Faguet.

Japan
As with the novel, essays existed in Japan several centuries before they developed in Europe with a genre of essays known as zuihitsu—loosely connected essays and fragmented ideas. Zuihitsu have existed since almost the beginnings of Japanese literature. Many of the most noted early works of Japanese literature are in this genre. Notable examples include The Pillow Book (c. 1000), by court lady Sei Shōnagon, and Tsurezuregusa (1330), by particularly renowned Japanese Buddhist monk Yoshida Kenkō. Kenkō described his short writings similarly to Montaigne, referring to them as "nonsensical thoughts" written in "idle hours". Another noteworthy difference from Europe is that women have traditionally written in Japan, though the more formal, Chinese-influenced writings of male writers were more prized at the time.

China
The eight-legged essay (Chinese: 八股文; pinyin: bāgǔwén; lit. 'eight bone text') was a style of essay in imperial examinations during the Ming and Qing dynasties in China. The eight-legged essay was needed for those test takers in these civil service tests to show their merits for government service, often focusing on Confucian thought and knowledge of the Four Books and Five Classics, in relation to governmental ideals. Test takers could not write in innovative or creative ways, but needed to conform to the standards of the eight-legged essay. Various skills were examined, including the ability to write coherently and to display basic logic. In certain times, the candidates were expected to spontaneously compose poetry upon a set theme, whose value was also sometimes questioned, or eliminated as part of the test material. This was a major argument in favor of the eight-legged essay, arguing that it were better to eliminate creative art in favor of prosaic literacy. In the history of Chinese literature, the eight-legged essay is often said to have caused China's "cultural stagnation and economic backwardness" in the 19th century.

Forms and styles
This section describes the different forms and styles of essay writing. These are used by an array of authors, including university students and professional essayists.

Cause and effect
The defining features of a "cause and effect" essay are causal chains that connect from a cause to an effect, careful language, and chronological or emphatic order. A writer using this rhetorical method must consider the subject, determine the purpose, consider the audience, think critically about different causes or consequences, consider a thesis statement, arrange the parts, consider the language, and decide on a conclusion.

Classification and division
Classification is the categorization of objects into a larger whole while division is the breaking of a larger whole into smaller parts.

Compare and contrast
Compare and contrast essays are characterized by a basis for comparison, points of comparison, and analogies. It is grouped by the object (chunking) or by point (sequential). The comparison highlights the similarities between two or more similar objects while contrasting highlights the differences between two or more objects. When writing a compare/contrast essay, writers need to determine their purpose, consider their audience, consider the basis and points of comparison, consider their thesis statement, arrange and develop the comparison, and reach a conclusion. Compare and contrast is arranged emphatically.

Expository
An expository essay is used to inform, describe or explain a topic, using important facts to teach the reader about a topic. Mostly written in third-person, using "it", "he", "she", "they," the expository essay uses formal language to discuss someone or something. Examples of expository essays are: a medical or biological condition, social or technological process, life or character of a famous person. The writing of an expository essay often consists of the following steps: organizing thoughts (brainstorming), researching a topic, developing a thesis statement, writing the introduction, writing the body of essay, and writing the conclusion. Expository essays are often assigned as a part of SAT and other standardized testing or as homework for high school and college students.

Descriptive
Descriptive writing is characterized by sensory details, which appeal to the physical senses, and details that appeal to a reader's emotional, physical, or intellectual sensibilities. Determining the purpose, considering the audience, creating a dominant impression, using descriptive language, and organizing the description are the rhetorical choices to consider when using a description. A description is usually arranged spatially but can also be chronological or emphatic. The focus of a description is the scene. Description uses tools such as denotative language, connotative language, figurative language, metaphor, and simile to arrive at a dominant impression. One university essay guide states that "descriptive writing says what happened or what another author has discussed; it provides an account of the topic". Lyric essays are an important form of descriptive essays.

Dialectic
In the dialectic form of the essay, which is commonly used in philosophy, the writer makes a thesis and argument, then objects to their own argument (with a counterargument), but then counters the counterargument with a final and novel argument. This form benefits from presenting a broader perspective while countering a possible flaw that some may present. This type is sometimes called an ethics paper.

Exemplification
An exemplification essay is characterized by a generalization and relevant, representative, and believable examples including anecdotes. Writers need to consider their subject, determine their purpose, consider their audience, decide on specific examples, and arrange all the parts together when writing an exemplification essay.

Familiar
An essayist writes a familiar essay if speaking to a single reader, writing about both themselves, and about particular subjects. Anne Fadiman notes that "the genre's heyday was the early nineteenth century," and that its greatest exponent was Charles Lamb. She also suggests that while critical essays have more brain than the heart, and personal essays have more heart than brain, familiar essays have equal measures of both.

History (thesis)
A history essay sometimes referred to as a thesis essay describes an argument or claim about one or more historical events and supports that claim with evidence, arguments, and references. The text makes it clear to the reader why the argument or claim is as such.

Narrative
A narrative uses tools such as flashbacks, flash-forwards, and transitions that often build to a climax. The focus of a narrative is the plot. When creating a narrative, authors must determine their purpose, consider their audience, establish their point of view, use dialogue, and organize the narrative. A narrative is usually arranged chronologically.

Argumentative
An argumentative essay is a critical piece of writing, aimed at presenting objective analysis of the subject matter, narrowed down to a single topic. The main idea of all the criticism is to provide an opinion either of positive or negative implication. As such, a critical essay requires research and analysis, strong internal logic and sharp structure. Its structure normally builds around introduction with a topic's relevance and a thesis statement, body paragraphs with arguments linking back to the main thesis, and conclusion. In addition, an argumentative essay may include a refutation section where conflicting ideas are acknowledged, described, and criticized. Each argument of an argumentative essay should be supported with sufficient evidence, relevant to the point.

Process
A process essay is used for an explanation of making or breaking something. Often, it is written in chronological order or numerical order to show step-by-step processes. It has all the qualities of a technical document with the only difference is that it is often written in descriptive mood, while a technical document is mostly in imperative mood.

Economic
An economic essay can start with a thesis, or it can start with a theme. It can take a narrative course and a descriptive course. It can even become an argumentative essay if the author feels the need. After the introduction, the author has to do his/her best to expose the economic matter at hand, to analyze it, evaluate it, and draw a conclusion. If the essay takes more of a narrative form then the author has to expose each aspect of the economic puzzle in a way that makes it clear and understandable for the reader

Reflective
A reflective essay is an analytical piece of writing in which the writer describes a real or imaginary scene, event, interaction, passing thought, memory, or form—adding a personal reflection on the meaning of the topic in the author's life. Thus, the focus is not merely descriptive. The writer doesn't just describe the situation, but revisits the scene with more detail and emotion to examine what went well, or reveal a need for additional learning—and may relate what transpired to the rest of the author's life.

Other logical structures
The logical progression and organizational structure of an essay can take many forms. Understanding how the movement of thought is managed through an essay has a profound impact on its overall cogency and ability to impress. A number of alternative logical structures for essays have been visualized as diagrams, making them easy to implement or adapt in the construction of an argument.

Academic

In countries like the United States and the United Kingdom, essays have become a major part of a formal education in the form of free response questions. Secondary students in these countries are taught structured essay formats to improve their writing skills, and essays are often used by universities in these countries in selecting applicants (see admissions essay). In both secondary and tertiary education, essays are used to judge the mastery and comprehension of the material. Students are asked to explain, comment on, or assess a topic of study in the form of an essay. In some courses, university students must complete one or more essays over several weeks or months. In addition, in fields such as the humanities and social sciences, mid-term and end of term examinations often require students to write a short essay in two or three hours.

In these countries, so-called academic essays, also called papers, are usually more formal than literary ones. They may still allow the presentation of the writer's own views, but this is done in a logical and factual manner, with the use of the first person often discouraged. Longer academic essays (often with a word limit of between 2,000 and 5,000 words) are often more discursive. They sometimes begin with a short summary analysis of what has previously been written on a topic, which is often called a literature review.

Longer essays may also contain an introductory page that defines words and phrases of the essay's topic. Most academic institutions require that all substantial facts, quotations, and other supporting material in an essay be referenced in a bibliography or works cited page at the end of the text. This scholarly convention helps others (whether teachers or fellow scholars) to understand the basis of facts and quotations the author uses to support the essay's argument. The bibliography also helps readers evaluate to what extent the argument is supported by evidence and to evaluate the quality of that evidence. The academic essay tests the student's ability to present their thoughts in an organized way and is designed to test their intellectual capabilities.

One of the challenges facing universities is that in some cases, students may submit essays purchased from an essay mill (or "paper mill") as their own work. An "essay mill" is a ghostwriting service that sells pre-written essays to university and college students. Since plagiarism is a form of academic dishonesty or academic fraud, universities and colleges may investigate papers they suspect are from an essay mill by using plagiarism detection software, which compares essays against a database of known mill essays and by orally testing students on the contents of their papers.

Magazine or newspaper
Essays often appear in magazines, especially magazines with an intellectual bent, such as The Atlantic and Harpers. Magazine and newspaper essays use many of the essay types described in the section on forms and styles (e.g., descriptive essays, narrative essays, etc.). Some newspapers also print essays in the op-ed section.

Employment
Employment essays detailing experience in a certain occupational field are required when applying for some jobs, especially government jobs in the United States. Essays known as Knowledge Skills and Executive Core Qualifications are required when applying to certain US federal government positions.

A KSA, or "Knowledge, Skills, and Abilities", is a series of narrative statements that are required when applying to Federal government job openings in the United States. KSAs are used along with resumes to determine who the best applicants are when several candidates qualify for a job. The knowledge, skills, and abilities necessary for the successful performance of a position are contained on each job vacancy announcement. KSAs are brief and focused essays about one's career and educational background that presumably qualify one to perform the duties of the position being applied for.

An Executive Core Qualification, or ECQ, is a narrative statement that is required when applying to Senior Executive Service positions within the US Federal government. Like the KSAs, ECQs are used along with resumes to determine who the best applicants are when several candidates qualify for a job. The Office of Personnel Management has established five executive core qualifications that all applicants seeking to enter the Senior Executive Service must demonstrate.

Film
A film essay (also essay film or cinematic essay) consists of the evolution of a theme or an idea rather than a plot per se, or the film literally being a cinematic accompaniment to a narrator reading an essay. From another perspective, an essay film could be defined as a documentary film visual basis combined with a form of commentary that contains elements of self-portrait (rather than autobiography), where the signature (rather than the life story) of the filmmaker is apparent. The cinematic essay often blends documentary, fiction, and experimental film making using tones and editing styles.

The genre is not well-defined but might include propaganda works of early Soviet filmmakers like Dziga Vertov, present-day filmmakers including Chris Marker, Michael Moore (Roger & Me, Bowling for Columbine and Fahrenheit 9/11), Errol Morris (The Thin Blue Line), Morgan Spurlock (Supersize Me) and Agnès Varda. Jean-Luc Godard describes his recent work as "film-essays". Two filmmakers whose work was the antecedent to the cinematic essay include Georges Méliès and Bertolt Brecht. Méliès made a short film (The Coronation of Edward VII (1902)) about the 1902 coronation of King Edward VII, which mixes actual footage with shots of a recreation of the event. Brecht was a playwright who experimented with film and incorporated film projections into some of his plays. Orson Welles made an essay film in his own pioneering style, released in 1974, called F for Fake, which dealt specifically with art forger Elmyr de Hory and with the themes of deception, "fakery", and authenticity in general.

David Winks Gray's article "The essay film in action" states that the "essay film became an identifiable form of filmmaking in the 1950s and '60s". He states that since that time, essay films have tended to be "on the margins" of the filmmaking the world. Essay films have a "peculiar searching, questioning tone ... between documentary and fiction" but without "fitting comfortably" into either genre. Gray notes that just like written essays, essay films "tend to marry the personal voice of a guiding narrator (often the director) with a wide swath of other voices". The University of Wisconsin Cinematheque website echoes some of Gray's comments; it calls a film essay an "intimate and allusive" genre that "catches filmmakers in a pensive mood, ruminating on the margins between fiction and documentary" in a manner that is "refreshingly inventive, playful, and idiosyncratic".

Video
Video essays are an emerging media type similar to film essays. Video essays have gained significant prominence on YouTube, as YouTube's policies on free uploads of arbitrary lengths have made it a hotbed. Some video essays feature long, documentary style writing and editing, going deep into the research and history of a particular topic. Others are more akin to an argumentative essay in which a single argument is developed and supported throughout the video. Video essay styles have become especially prominent among BreadTube creators such as ContraPoints and PhilosophyTube.

Music
In the realm of music, composer Samuel Barber wrote a set of "Essays for Orchestra", relying on the form and content of the music to guide the listener's ear, rather than any extra-musical plot or story.

Photography

A photographic essay strives to cover a topic with a linked series of photographs. Photo essays range from purely photographic works to photographs with captions or small notes to full-text essays with a few or many accompanying photographs. Photo essays can be sequential in nature, intended to be viewed in a particular order—or they may consist of non-ordered photographs viewed all at once or in an order that the viewer chooses. All photo essays are collections of photographs, but not all collections of photographs are photo essays. Photo essays often address a certain issue or attempt to capture the character of places and events.

Visual arts
In the visual arts, an essay is a preliminary drawing or sketch that forms a basis for a final painting or sculpture, made as a test of the work's composition (this meaning of the term, like several of those following, comes from the word essay's meaning of "attempt" or "trial").

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Essay


text:
Error detection and correction

In information theory and coding theory with applications in computer science and telecommunication, error detection and correction (EDAC) or error control are techniques that enable reliable delivery of digital data over unreliable communication channels. Many communication channels are subject to channel noise, and thus errors may be introduced during transmission from the source to a receiver. Error detection techniques allow detecting such errors, while error correction enables reconstruction of the original data in many cases.

Definitions
Error detection is the detection of errors caused by noise or other impairments during transmission from the transmitter to the receiver.

Error correction is the detection of errors and reconstruction of the original, error-free data.

History
In classical antiquity, copyists of the Hebrew Bible were paid for their work according to the number of stichs (lines of verse). As the prose books of the Bible were hardly ever written in stichs, the copyists, in order to estimate the amount of work, had to count the letters. This also helped ensure accuracy in the transmission of the text with the production of subsequent copies. Between the 7th and 10th centuries CE a group of Jewish scribes formalized and expanded this to create the Numerical Masorah to ensure accurate reproduction of the sacred text. It included counts of the number of words in a line, section, book and groups of books, noting the middle stich of a book, word use statistics, and commentary. Standards became such that a deviation in even a single letter in a Torah scroll was considered unacceptable. The effectiveness of their error correction method was verified by the accuracy of copying through the centuries demonstrated by discovery of the Dead Sea Scrolls in 1947–1956, dating from c. 150 BCE-75 CE.

The modern development of error correction codes is credited to Richard Hamming in 1947. A description of Hamming's code appeared in Claude Shannon's A Mathematical Theory of Communication and was quickly generalized by Marcel J. E. Golay.

Principles
All error-detection and correction schemes add some redundancy (i.e., some extra data) to a message, which receivers can use to check consistency of the delivered message and to recover data that has been determined to be corrupted. Error detection and correction schemes can be either systematic or non-systematic. In a systematic scheme, the transmitter sends the original (error-free) data and attaches a fixed number of check bits (or parity data), which are derived from the data bits by some encoding algorithm. If error detection is required, a receiver can simply apply the same algorithm to the received data bits and compare its output with the received check bits; if the values do not match, an error has occurred at some point during the transmission. If error correction is required, a receiver can apply the decoding algorithm to the received data bits and the received check bits to recover the original error-free data. In a system that uses a non-systematic code, the original message is transformed into an encoded message carrying the same information and that has at least as many bits as the original message.

Good error control performance requires the scheme to be selected based on the characteristics of the communication channel. Common channel models include memoryless models where errors occur randomly and with a certain probability, and dynamic models where errors occur primarily in bursts. Consequently, error-detecting and correcting codes can be generally distinguished between random-error-detecting/correcting and burst-error-detecting/correcting. Some codes can also be suitable for a mixture of random errors and burst errors.

If the channel characteristics cannot be determined, or are highly variable, an error-detection scheme may be combined with a system for retransmissions of erroneous data. This is known as automatic repeat request (ARQ), and is most notably used in the Internet. An alternate approach for error control is hybrid automatic repeat request (HARQ), which is a combination of ARQ and error-correction coding.

Types of error correction
There are three major types of error correction:

Automatic repeat request
Automatic repeat request (ARQ) is an error control method for data transmission that makes use of error-detection codes, acknowledgment and/or negative acknowledgment messages, and timeouts to achieve reliable data transmission. An acknowledgment is a message sent by the receiver to indicate that it has correctly received a data frame.

Usually, when the transmitter does not receive the acknowledgment before the timeout occurs (i.e., within a reasonable amount of time after sending the data frame), it retransmits the frame until it is either correctly received or the error persists beyond a predetermined number of retransmissions.

Three types of ARQ protocols are Stop-and-wait ARQ, Go-Back-N ARQ, and Selective Repeat ARQ.

ARQ is appropriate if the communication channel has varying or unknown capacity, such as is the case on the Internet. However, ARQ requires the availability of a back channel, results in possibly increased latency due to retransmissions, and requires the maintenance of buffers and timers for retransmissions, which in the case of network congestion can put a strain on the server and overall network capacity.

For example, ARQ is used on shortwave radio data links in the form of ARQ-E, or combined with multiplexing as ARQ-M.

Forward error correction
Forward error correction (FEC) is a process of adding redundant data such as an error-correcting code (ECC) to a message so that it can be recovered by a receiver even when a number of errors (up to the capability of the code being used) are introduced, either during the process of transmission or on storage. Since the receiver does not have to ask the sender for retransmission of the data, a backchannel is not required in forward error correction. Error-correcting codes are used in lower-layer communication such as cellular network, high-speed fiber-optic communication and Wi-Fi, as well as for reliable storage in media such as flash memory, hard disk and RAM.

Error-correcting codes are usually distinguished between convolutional codes and block codes:
 * Convolutional codes are processed on a bit-by-bit basis. They are particularly suitable for implementation in hardware, and the Viterbi decoder allows optimal decoding.
 * Block codes are processed on a block-by-block basis. Early examples of block codes are repetition codes, Hamming codes and multidimensional parity-check codes. They were followed by a number of efficient codes, Reed–Solomon codes being the most notable due to their current widespread use. Turbo codes and low-density parity-check codes (LDPC) are relatively new constructions that can provide almost optimal efficiency.

Shannon's theorem is an important theorem in forward error correction, and describes the maximum information rate at which reliable communication is possible over a channel that has a certain error probability or signal-to-noise ratio (SNR). This strict upper limit is expressed in terms of the channel capacity. More specifically, the theorem says that there exist codes such that with increasing encoding length the probability of error on a discrete memoryless channel can be made arbitrarily small, provided that the code rate is smaller than the channel capacity. The code rate is defined as the fraction k/n of k source symbols and n encoded symbols.

The actual maximum code rate allowed depends on the error-correcting code used, and may be lower. This is because Shannon's proof was only of existential nature, and did not show how to construct codes that are both optimal and have efficient encoding and decoding algorithms.

Hybrid schemes
Hybrid ARQ is a combination of ARQ and forward error correction. There are two basic approaches:
 * Messages are always transmitted with FEC parity data (and error-detection redundancy). A receiver decodes a message using the parity information and requests retransmission using ARQ only if the parity data was not sufficient for successful decoding (identified through a failed integrity check).
 * Messages are transmitted without parity data (only with error-detection information). If a receiver detects an error, it requests FEC information from the transmitter using ARQ and uses it to reconstruct the original message.

The latter approach is particularly attractive on an erasure channel when using a rateless erasure code.

Types of error detection
Error detection is most commonly realized using a suitable hash function (or specifically, a checksum, cyclic redundancy check or other algorithm). A hash function adds a fixed-length tag to a message, which enables receivers to verify the delivered message by recomputing the tag and comparing it with the one provided.

There exists a vast variety of different hash function designs. However, some are of particularly widespread use because of either their simplicity or their suitability for detecting certain kinds of errors (e.g., the cyclic redundancy check's performance in detecting burst errors).

Minimum distance coding
A random-error-correcting code based on minimum distance coding can provide a strict guarantee on the number of detectable errors, but it may not protect against a preimage attack.

Repetition codes
A repetition code is a coding scheme that repeats the bits across a channel to achieve error-free communication. Given a stream of data to be transmitted, the data are divided into blocks of bits. Each block is transmitted some predetermined number of times. For example, to send the bit pattern 1011, the four-bit block can be repeated three times, thus producing 1011 1011 1011. If this twelve-bit pattern was received as 1010 1011 1011 – where the first block is unlike the other two – an error has occurred.

A repetition code is very inefficient and can be susceptible to problems if the error occurs in exactly the same place for each group (e.g., 1010 1010 1010 in the previous example would be detected as correct). The advantage of repetition codes is that they are extremely simple, and are in fact used in some transmissions of numbers stations.

Parity bit
A parity bit is a bit that is added to a group of source bits to ensure that the number of set bits (i.e., bits with value 1) in the outcome is even or odd. It is a very simple scheme that can be used to detect single or any other odd number (i.e., three, five, etc.) of errors in the output. An even number of flipped bits will make the parity bit appear correct even though the data is erroneous.

Parity bits added to each word sent are called transverse redundancy checks, while those added at the end of a stream of words are called longitudinal redundancy checks. For example, if each of a series of m-bit words has a parity bit added, showing whether there were an odd or even number of ones in that word, any word with a single error in it will be detected. It will not be known where in the word the error is, however. If, in addition, after each stream of n words a parity sum is sent, each bit of which shows whether there were an odd or even number of ones at that bit-position sent in the most recent group, the exact position of the error can be determined and the error corrected. This method is only guaranteed to be effective, however, if there are no more than 1 error in every group of n words. With more error correction bits, more errors can be detected and in some cases corrected.

There are also other bit-grouping techniques.

Checksum
A checksum of a message is a modular arithmetic sum of message code words of a fixed word length (e.g., byte values). The sum may be negated by means of a ones'-complement operation prior to transmission to detect unintentional all-zero messages.

Checksum schemes include parity bits, check digits, and longitudinal redundancy checks. Some checksum schemes, such as the Damm algorithm, the Luhn algorithm, and the Verhoeff algorithm, are specifically designed to detect errors commonly introduced by humans in writing down or remembering identification numbers.

Cyclic redundancy check
A cyclic redundancy check (CRC) is a non-secure hash function designed to detect accidental changes to digital data in computer networks. It is not suitable for detecting maliciously introduced errors. It is characterized by specification of a generator polynomial, which is used as the divisor in a polynomial long division over a finite field, taking the input data as the dividend. The remainder becomes the result.

A CRC has properties that make it well suited for detecting burst errors. CRCs are particularly easy to implement in hardware and are therefore commonly used in computer networks and storage devices such as hard disk drives.

The parity bit can be seen as a special-case 1-bit CRC.

Cryptographic hash function
The output of a cryptographic hash function, also known as a message digest, can provide strong assurances about data integrity, whether changes of the data are accidental (e.g., due to transmission errors) or maliciously introduced. Any modification to the data will likely be detected through a mismatching hash value. Furthermore, given some hash value, it is typically infeasible to find some input data (other than the one given) that will yield the same hash value. If an attacker can change not only the message but also the hash value, then a keyed hash or message authentication code (MAC) can be used for additional security. Without knowing the key, it is not possible for the attacker to easily or conveniently calculate the correct keyed hash value for a modified message.

Error correction code
Any error-correcting code can be used for error detection. A code with minimum Hamming distance, d, can detect up to d − 1 errors in a code word. Using minimum-distance-based error-correcting codes for error detection can be suitable if a strict limit on the minimum number of errors to be detected is desired.

Codes with minimum Hamming distance d = 2 are degenerate cases of error-correcting codes and can be used to detect single errors. The parity bit is an example of a single-error-detecting code.

Applications
Applications that require low latency (such as telephone conversations) cannot use automatic repeat request (ARQ); they must use forward error correction (FEC). By the time an ARQ system discovers an error and re-transmits it, the re-sent data will arrive too late to be usable.

Applications where the transmitter immediately forgets the information as soon as it is sent (such as most television cameras) cannot use ARQ; they must use FEC because when an error occurs, the original data is no longer available.

Applications that use ARQ must have a return channel; applications having no return channel cannot use ARQ.

Applications that require extremely low error rates (such as digital money transfers) must use ARQ due to the possibility of uncorrectable errors with FEC.

Reliability and inspection engineering also make use of the theory of error-correcting codes.

Internet
In a typical TCP/IP stack, error control is performed at multiple levels:
 * Each Ethernet frame uses CRC-32 error detection. Frames with detected errors are discarded by the receiver hardware.
 * The IPv4 header contains a checksum protecting the contents of the header. Packets with incorrect checksums are dropped within the network or at the receiver.
 * The checksum was omitted from the IPv6 header in order to minimize processing costs in network routing and because current link layer technology is assumed to provide sufficient error detection (see also RFC 3819).
 * UDP has an optional checksum covering the payload and addressing information in the UDP and IP headers. Packets with incorrect checksums are discarded by the network stack. The checksum is optional under IPv4, and required under IPv6. When omitted, it is assumed the data-link layer provides the desired level of error protection.
 * TCP provides a checksum for protecting the payload and addressing information in the TCP and IP headers. Packets with incorrect checksums are discarded by the network stack and eventually get retransmitted using ARQ, either explicitly (such as through three-way handshake) or implicitly due to a timeout.

Deep-space telecommunications
The development of error-correction codes was tightly coupled with the history of deep-space missions due to the extreme dilution of signal power over interplanetary distances, and the limited power availability aboard space probes. Whereas early missions sent their data uncoded, starting in 1968, digital error correction was implemented in the form of (sub-optimally decoded) convolutional codes and Reed–Muller codes. The Reed–Muller code was well suited to the noise the spacecraft was subject to (approximately matching a bell curve), and was implemented for the Mariner spacecraft and used on missions between 1969 and 1977.

The Voyager 1 and Voyager 2 missions, which started in 1977, were designed to deliver color imaging and scientific information from Jupiter and Saturn. This resulted in increased coding requirements, and thus, the spacecraft were supported by (optimally Viterbi-decoded) convolutional codes that could be concatenated with an outer Golay (24,12,8) code. The Voyager 2 craft additionally supported an implementation of a Reed–Solomon code. The concatenated Reed–Solomon–Viterbi (RSV) code allowed for very powerful error correction, and enabled the spacecraft's extended journey to Uranus and Neptune. After ECC system upgrades in 1989, both crafts used V2 RSV coding.

The Consultative Committee for Space Data Systems currently recommends usage of error correction codes with performance similar to the Voyager 2 RSV code as a minimum. Concatenated codes are increasingly falling out of favor with space missions, and are replaced by more powerful codes such as Turbo codes or LDPC codes.

The different kinds of deep space and orbital missions that are conducted suggest that trying to find a one-size-fits-all error correction system will be an ongoing problem. For missions close to Earth, the nature of the noise in the communication channel is different from that which a spacecraft on an interplanetary mission experiences. Additionally, as a spacecraft increases its distance from Earth, the problem of correcting for noise becomes more difficult.

Satellite broadcasting
The demand for satellite transponder bandwidth continues to grow, fueled by the desire to deliver television (including new channels and high-definition television) and IP data. Transponder availability and bandwidth constraints have limited this growth. Transponder capacity is determined by the selected modulation scheme and the proportion of capacity consumed by FEC.

Data storage
Error detection and correction codes are often used to improve the reliability of data storage media. A parity track capable of detecting single-bit errors was present on the first magnetic tape data storage in 1951. The optimal rectangular code used in group coded recording tapes not only detects but also corrects single-bit errors. Some file formats, particularly archive formats, include a checksum (most often CRC32) to detect corruption and truncation and can employ redundancy or parity files to recover portions of corrupted data. Reed-Solomon codes are used in compact discs to correct errors caused by scratches.

Modern hard drives use Reed–Solomon codes to detect and correct minor errors in sector reads, and to recover corrupted data from failing sectors and store that data in the spare sectors. RAID systems use a variety of error correction techniques to recover data when a hard drive completely fails. Filesystems such as ZFS or Btrfs, as well as some RAID implementations, support data scrubbing and resilvering, which allows bad blocks to be detected and (hopefully) recovered before they are used. The recovered data may be re-written to exactly the same physical location, to spare blocks elsewhere on the same piece of hardware, or the data may be rewritten onto replacement hardware.

Error-correcting memory
Dynamic random-access memory (DRAM) may provide stronger protection against soft errors by relying on error-correcting codes. Such error-correcting memory, known as ECC or EDAC-protected memory, is particularly desirable for mission-critical applications, such as scientific computing, financial, medical, etc. as well as extraterrestrial applications due to the increased radiation in space.

Error-correcting memory controllers traditionally use Hamming codes, although some use triple modular redundancy. Interleaving allows distributing the effect of a single cosmic ray potentially upsetting multiple physically neighboring bits across multiple words by associating neighboring bits to different words. As long as a single-event upset (SEU) does not exceed the error threshold (e.g., a single error) in any particular word between accesses, it can be corrected (e.g., by a single-bit error-correcting code), and the illusion of an error-free memory system may be maintained.

In addition to hardware providing features required for ECC memory to operate, operating systems usually contain related reporting facilities that are used to provide notifications when soft errors are transparently recovered. One example is the Linux kernel's EDAC subsystem (previously known as Bluesmoke), which collects the data from error-checking-enabled components inside a computer system; besides collecting and reporting back the events related to ECC memory, it also supports other checksumming errors, including those detected on the PCI bus. A few systems also support memory scrubbing to catch and correct errors early before they become unrecoverable.

title: Error detection and correction


text:
Euclidean domain

In mathematics, more specifically in ring theory, a Euclidean domain (also called a Euclidean ring) is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of the Euclidean division of integers. This generalized Euclidean algorithm can be put to many of the same uses as Euclid's original algorithm in the ring of integers: in any Euclidean domain, one can apply the Euclidean algorithm to compute the greatest common divisor of any two elements. In particular, the greatest common divisor of any two elements exists and can be written as a linear combination of them (Bézout's identity). Also every ideal in a Euclidean domain is principal, which implies a suitable generalization of the fundamental theorem of arithmetic: every Euclidean domain is a unique factorization domain.

It is important to compare the class of Euclidean domains with the larger class of principal ideal domains (PIDs). An arbitrary PID has much the same "structural properties" of a Euclidean domain (or, indeed, even of the ring of integers), but when an explicit algorithm for Euclidean division is known, one may use the Euclidean algorithm and extended Euclidean algorithm to compute greatest common divisors and Bézout's identity. In particular, the existence of efficient algorithms for Euclidean division of integers and of polynomials in one variable over a field is of basic importance in computer algebra.

So, given an integral domain $R$, it is often very useful to know that $R$ has a Euclidean function: in particular, this implies that $R$ is a PID. However, if there is no "obvious" Euclidean function, then determining whether $R$ is a PID is generally a much easier problem than determining whether it is a Euclidean domain.

Euclidean domains appear in the following chain of class inclusions:

Definition
Let $R$ be an integral domain. A Euclidean function on $R$ is a function $f$ from $R \ {0}$to the non-negative integers satisfying the following fundamental division-with-remainder property:

 * (EF1) If $a$ and $b$ are in $R$ and $b$ is nonzero, then there exist $q$ and $r$ in $R$ such that $a = bq + r$ and either $r = 0$ or $f (r) < f (b)$.

A Euclidean domain is an integral domain which can be endowed with at least one Euclidean function. A particular Euclidean function $f$ is not part of the definition of a Euclidean domain, as, in general, a Euclidean domain may admit many different Euclidean functions.

In this context, $q$ and $r$ are called respectively a quotient and a remainder of the division (or Euclidean division) of $a$ by $b$. In contrast with the case of integers and polynomials, the quotient is generally not uniquely defined, but when a quotient has been chosen, the remainder is uniquely defined.

Most algebra texts require a Euclidean function to have the following additional property:

 * (EF2) For all nonzero $a$ and $b$ in $R$, $f (a) ≤ f (ab)$.

However, one can show that (EF1) alone suffices to define a Euclidean domain; if an integral domain $R$ is endowed with a function $g$ satisfying (EF1), then $R$ can also be endowed with a function satisfying both (EF1) and (EF2) simultaneously. Indeed, for $a$ in $R \ {0}$, one can define $f (a)$ as follows:

 * $$f(a) = \min_{x \in R \setminus \{0\}} g(xa)$$

In words, one may define $f (a)$ to be the minimum value attained by $g$ on the set of all non-zero elements of the principal ideal generated by $a$.

A Euclidean function $f$ is multiplicative if $f (ab) = f (a) f (b)$ and $f (a)$ is never zero. It follows that $f (1) = 1$. More generally, $f (a) = 1$ if and only if $a$ is a unit.

Notes on the definition
Many authors use other terms in place of "Euclidean function", such as "degree function", "valuation function", "gauge function" or "norm function". Some authors also require the domain of the Euclidean function to be the entire ring $R$; however, this does not essentially affect the definition, since (EF1) does not involve the value of $f (0)$. The definition is sometimes generalized by allowing the Euclidean function to take its values in any well-ordered set; this weakening does not affect the most important implications of the Euclidean property.

The property (EF1) can be restated as follows: for any principal ideal $I$ of $R$ with nonzero generator $b$, all nonzero classes of the quotient ring $R/I$ have a representative $r$ with $f (r) < f (b)$. Since the possible values of $f$ are well-ordered, this property can be established by showing that $f (r) < f (b)$ for any $r ∉ I$ with minimal value of $f (r)$ in its class. Note that, for a Euclidean function that is so established, there need not exist an effective method to determine $q$ and $r$ in (EF1).

Examples
Examples of Euclidean domains include:

 * Any field. Define $f (x) = 1$ for all nonzero $x$.
 * $Z$, the ring of integers. Define $f (n) = |n|$, the absolute value of $n$.
 * $Z[]$, the ring of Gaussian integers. Define $f (a + bi) = a2 + b2$, the norm of the Gaussian integer $a + bi$.
 * $Z[ω]$ (where $ω$ is a primitive (non-real) cube root of unity), the ring of Eisenstein integers. Define $f (a + bω) = a2 − ab + b2$, the norm of the Eisenstein integer $a + bω$.
 * $K[X]$, the ring of polynomials over a field $K$. For each nonzero polynomial $P$, define $f (P)$ to be the degree of $P$.
 * $K[X]$, the ring of formal power series over the field $K$. For each nonzero power series $P$, define $f (P)$ as the order of $P$, that is the degree of the smallest power of $X$ occurring in $P$. In particular, for two nonzero power series $P$ and $Q$, $f (P) ≤ f (Q)$ if and only if $P$ divides $Q$.
 * Any discrete valuation ring. Define $f (x)$ to be the highest power of the maximal ideal $M$ containing $x$. Equivalently, let $g$ be a generator of $M$, and $v$ be the unique integer such that $gv$ is an associate of $x$, then define $f (x) = v$. The previous example $K[X]$ is a special case of this.
 * A Dedekind domain with finitely many nonzero prime ideals $P1, ..., Pn$. Define $$f(x) = \sum_{i=1}^n v_i(x)$$, where $vi$ is the discrete valuation corresponding to the ideal $Pi$.

Examples of domains that are not Euclidean domains include:
 * Every domain that is not a principal ideal domain, such as the ring of polynomials in at least two indeterminates over a field, or the ring of univariate polynomials with integer coefficients, or the number ring $Z[]$.
 * The ring of integers of $Q$, consisting of the numbers $a + b√−19⁄2$ where $a$ and $b$ are integers and both even or both odd. It is a principal ideal domain that is not Euclidean.This was proved by Theodore Motzkin and was the first case known.
 * The ring $A = R[X, Y]/(X^{ 2} + Y^{ 2} + 1)$ is also a principal ideal domain that is not Euclidean. To see that it is not a Euclidean domain, it suffices to show that for every non-zero prime $$p\in A$$, the map $$A^\times\to(A/p)^\times$$ induced by the quotient map $$A\to A/p$$ is not surjective.

Properties
Let R be a domain and f a Euclidean function on R. Then:

 * R is a principal ideal domain (PID). In fact, if I is a nonzero ideal of R then any element a of I \ {0} with minimal value (on that set) of f(a) is a generator of I. As a consequence R is also a unique factorization domain and a Noetherian ring. With respect to general principal ideal domains, the existence of factorizations (i.e., that R is an atomic domain) is particularly easy to prove in Euclidean domains: choosing a Euclidean function f satisfying (EF2), x cannot have any decomposition into more than f(x) nonunit factors, so starting with x and repeatedly decomposing reducible factors is bound to produce a factorization into irreducible elements.
 * Any element of R at which f takes its globally minimal value is invertible in R. If an f satisfying (EF2) is chosen, then the converse also holds, and f takes its minimal value exactly at the invertible elements of R.
 * If Euclidean division is algorithmic, that is, if there is an algorithm for computing the quotient and the remainder, then an extended Euclidean algorithm can be defined exactly as in the case of integers.
 * If a Euclidean domain is not a field then it has an element a with the following property: any element x not divisible by a can be written as x = ay + u for some unit u and some element y. This follows by taking a to be a non-unit with f(a) as small as possible. This strange property can be used to show that some principal ideal domains are not Euclidean domains, as not all PIDs have this property. For example, for d = −19, −43, −67, −163, the ring of integers of $$\mathbf{Q}(\sqrt{d}\,)$$ is a PID which is  Euclidean, but the cases d = −1, −2, −3, −7, −11  Euclidean.

However, in many finite extensions of Q with trivial class group, the ring of integers is Euclidean (not necessarily with respect to the absolute value of the field norm; see below). Assuming the extended Riemann hypothesis, if K is a finite extension of Q and the ring of integers of K is a PID with an infinite number of units, then the ring of integers is Euclidean. In particular this applies to the case of totally real quadratic number fields with trivial class group. In addition (and without assuming ERH), if the field K is a Galois extension of Q, has trivial class group and unit rank strictly greater than three, then the ring of integers is Euclidean. An immediate corollary of this is that if the number field is Galois over Q, its class group is trivial and the extension has degree greater than 8 then the ring of integers is necessarily Euclidean.

Norm-Euclidean fields
Algebraic number fields K come with a canonical norm function on them: the absolute value of the field norm N that takes an algebraic element α to the product of all the conjugates of α. This norm maps the ring of integers of a number field K, say OK, to the nonnegative rational integers, so it is a candidate to be a Euclidean norm on this ring. If this norm satisfies the axioms of a Euclidean function then the number field K is called norm-Euclidean or simply Euclidean. Strictly speaking it is the ring of integers that is Euclidean since fields are trivially Euclidean domains, but the terminology is standard.

If a field is not norm-Euclidean then that does not mean the ring of integers is not Euclidean, just that the field norm does not satisfy the axioms of a Euclidean function. In fact, the rings of integers of number fields may be divided in several classes:
 * Those that are not principal and therefore not Euclidean, such as the integers of $$\mathbf{Q}(\sqrt{-5}\,)$$
 * Those that are principal and not Euclidean, such as the integers of $$\mathbf{Q}(\sqrt{-19}\,)$$
 * Those that are Euclidean and not norm-Euclidean, such as the integers of $$\mathbf{Q}(\sqrt{69}\,)$$
 * Those that are norm-Euclidean, such as Gaussian integers (integers of $$\mathbf{Q}(\sqrt{-1}\,)$$)

The norm-Euclidean quadratic fields have been fully classified; they are $$\mathbf{Q}(\sqrt{d}\,)$$ where $$d$$ takes the values
 * −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73.

Every Euclidean imaginary quadratic field is norm-Euclidean and is one of the five first fields in the preceding list.

title: Euclidean domain