# Constraint counting

﻿
Constraint counting

In mathematics, constraint counting is a crude but often useful way of counting the number of free functions needed to specify a solution to a partial differential equation.

## Einstein strength

Everyone knows that Albert Einstein said that a physical theory should be as simple as possible, but no simpler. But not everyone knows that he had a quantitative idea in mind.[citation needed]

Consider a second order partial differential equation in three variables, such as the two-dimensional wave equation

utt = uxx + uyy.

It is often profitable to think of such an equation as a rewrite rule allowing us to rewrite arbitrary partial derivatives of the function u(t,x,y) using fewer partials than would be needed for an arbitrary function. For example, if u satisfies the wave equation, we can rewrite

utyt = utty = uxxy + uyyy

where in the first equality, we appealed to the fact that partial derivatives commute.

Einstein asked: how much redundancy can we eliminate in this fashion, for a given partial differential equation?

### Linear equations

To answer this in the important special case of a linear partial differential equation, Einstein asked: how many of the partial derivatives of a solution can be linearly independent? It is convenient to record his answer using an ordinary generating function $s(\xi) = \sum_{k=0}^\infty s_k \xi^k$

where sk is a natural number counting the number of linearly independent partial derivatives (of order k) of an arbitrary function in the solution space of the equation in question.

Einstein observed that whenever a function satisfies some partial differential equation, we can use the corresponding rewrite rule to eliminate some of them, because further mixed partials have necessarily become linearly dependent. Specifically, the power series counting the variety of arbitrary functions of three variables (no constraints) is $f(\xi) = \frac{1}{(1-\xi)^3} = 1 + 3 \xi + 6 \xi^2 + 10 \xi^3 + \dots$

but the power series counting those in the solution space of some second order p.d.e. is $g(\xi) = \frac{1-\xi^2}{(1-\xi)^3} = 1 + 2 \xi + 5 \xi^2 + 7 \xi^3 + \dots$

which records that we can eliminate one second order partial utt, three third order partials $u_{ttt}, \, u_{ttx}, \, u_{tty}$, and so forth.

More generally, the o.g.f. for an arbitrary function of n variables is $s[n](\xi) = 1/(1-\xi)^n = 1 + n \, \xi + \left( \begin{matrix} n \\ 2 \end{matrix} \right) \, \xi^2 + \left( \begin{matrix} n+1 \\ 3 \end{matrix} \right) \, \xi^3 + \dots$

where the coefficients of the infinite power series of the generating function are constructed using an appropriate infinite sequence of binomial coefficients, and the power series for a function required to satisfy a linear m-th order equation is $g(\xi) = \frac{1-\xi^m}{(1-\xi)^n}$

Next, $\frac{1-\xi^2}{(1-\xi)^3} = \frac{1 + \xi}{(1-\xi)^2}$

which can be interpreted to predict that a solution to a second order linear p.d.e. in three variables is expressible by two freely chosen functions of two variables, one of which is used immediately, and the second, only after taking a first derivative, in order to express the solution.

### General solution of initial value problem

To verify this prediction, recall the solution of the initial value problem $u_{tt} = u_{xx} + u_{yy}, \; u(0,x,y) = p(x,y), \; u_t(0,x,y) = q(x,y)$

Applying the Laplace transform $u(t,x,y) \mapsto [Lu](\omega,x,y)$ gives $-\omega^2 \, [Lu] + \omega \, p(x,y) + q(x,y) + [Lu]_x + [Lu]_y$

Applying the Fourier transform $[Lu](\omega,x,y) \mapsto [FLU](\omega,m,n)$ to the two spatial variables gives $-\omega^2 \, [FLu] + \omega \, [Fp] + [Fq] - (m^2+n^2) \, [FLu]$

or $[FLu](\omega,m,n) = \frac{ \omega \, [Fp](m,n) + [Fq](m,n)}{\omega^2 + m^2 + n^2}$

Applying the inverse Laplace transform gives $[Fu](t,m,n) = [Fp](m,n) \, \cos( \sqrt{m^2+n^2} \, t ) + \frac{ [Fq](m,n) \, \sin (\sqrt{m^2+n^2} \, t) }{\sqrt{m^2+n^2}}$

Applying the inverse Fourier transform gives

u(t,x,y) = Q(t,x,y) + Pt(t,x,y)

where $P(t,x,y) = \frac{1}{2\pi} \, \int_{(x-x')^2 + (y-y')^2 < t^2} \frac{p(x',y') \, dx' dy'}{ \left[ t^2-(x-x')^2-(y-y')^2 \right]^{1/2}}$ $Q(t,x,y) = \frac{1}{2\pi} \, \int_{(x-x')^2 + (y-y')^2 < t^2} \frac{q(x',y') \, dx' dy'}{ \left[ t^2-(x-x')^2-(y-y')^2 \right]^{1/2}}$

Here, p,q are arbitrary (sufficiently smooth) functions of two variables, so (due their modest time dependence) the integrals P,Q also count as "freely chosen" functions of two variables; as promised, one of them is differentiated once before adding to the other to express the general solution of the initial value problem for the two dimensional wave equation.

### Quasilinear equations

In the case of a nonlinear equation, it will only rarely be possible to obtain the general solution in closed form. However, if the equation is quasilinear (linear in the highest order derivatives), then we can still obtain approximate information similar to the above: specifying a member of the solution space will be "modulo nonlinear quibbles" equivalent to specifying a certain number of functions in a smaller number of variables. The number of these functions is the Einstein strength of the p.d.e. In the simple example above, the strength is two, although in this case we were able to obtain more precise information.

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Decomposition method (constraint satisfaction) — In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and acyclic. Decomposition methods work by grouping variables into sets, and solving a… …   Wikipedia

• List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

• Exact solutions in general relativity — In general relativity, an exact solution is a Lorentzian manifold equipped with certain tensor fields which are taken to model states of ordinary matter, such as a fluid, or classical nongravitational fields such as the electromagnetic field.… …   Wikipedia

• Mathematics of Sudoku — The class of Sudoku puzzles consists of a partially completed row column grid of cells partitioned into N regions each of size N cells, to be filled in using a prescribed set of N distinct symbols (typically the numbers {1, ..., N}), so that each …   Wikipedia

• 2-satisfiability — In computer science, 2 satisfiability (abbreviated as 2 SAT or just 2SAT) is the problem of determining whether a collection of two valued (Boolean or binary) variables with constraints on pairs of variables can be assigned values satisfying all… …   Wikipedia

• Association rule learning — In data mining, association rule learning is a popular and well researched method for discovering interesting relations between variables in large databases. Piatetsky Shapiro describes analyzing and presenting strong rules discovered in… …   Wikipedia

• Garbage collection (computer science) — This article is about garbage collection in memory management. For garbage collection in an SSD, see garbage collection (SSD). For other uses, see garbage collection. In computer science, garbage collection (GC) is a form of automatic memory… …   Wikipedia

• Clique problem — The brute force algorithm finds a 4 clique in this 7 vertex graph (the complement of the 7 vertex path graph) by systematically checking all C(7,4)=35 4 vertex subgraphs for completeness. In computer science, the clique problem refers to any of… …   Wikipedia

• Pythagoreans and Eleatics — Edward Hussey PYTHAGORAS AND THE EARLY PYTHAGOREANS Pythagoras, a native of Samos, emigrated to southern Italy around 520, and seems to have established himself in the city of Croton. There he founded a society of people sharing his beliefs and… …   History of philosophy

• Polyhedral combinatorics — is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher dimensional convex polytopes.A key question in polyhedral combinatorics is to… …   Wikipedia