For functions f on the discrete circle {0,…,N-1} this program computes their uncentered maximal functions and the ratio of the L^p norms of the kth derivative of the maximal function and the function.

Building

If git is installed you can fetch the repository using

git clone https://cgit.jnwt.eu/discretemf

The program is written in C and hence requires a C compiler for building. If make and gcc are installed then running

make

builds three files:

• charf_approx does computations using floating point (double) numbers, which come with rounding errors.
• charf_error does computations using floating point (double) numbers and gives an upper bound for the total rounding error.
• charf_exact does exact computations using fractions. Nominator and denominator are of type unsigned long long and bounded in size accordingly.

Computation

By default, the program goes through all characteristic functions on circles from length 2 to 36, considers derivatives from order 0 to 64 and exponents p = 1,2,4,8,∞. Computing the maximal function of a function is the most computationally complex part. This means it is time efficient to consider several orders of derivative and exponents at the same time, in particular since the (k+1)th derivative is computed using the kth derivative.

The program continuously outputs whenever it finds a function that beats the last record for the largest ratio of the L^p norm of the kth derivative of the maximal function and the function. It is also possible to print the results in human readable format and as a latex table.

Error bounds

Even for a characteristic function that only take values 0 or 1, its maximal function may not be integer valued. The most widespread way to do non integer arithmetic on a computer is floating point arithmetic. This however is not exact, so results cannot be trusted a priori. This program implements two alternative ways to make results reliable:

1. Interval arithmetic: To each floating point variable we assign an confidence interval, in which we know the true value has to lie. In this model arithmetic operations act on pairs of floating point numbers: the estimated value and the length of the confidence interval. I am relatively confident that the computed confidence intervals are correct for all operations except exponentiation, which is not used for p = 1,∞.
2. Rational numbers: For integer and even rational valued functions also the maximal function is rational valued. Thus, by storing values as fractions the maximal function and all derivatives can be computed exactly, and so can L^p norms for p = 1,∞. The downside of this method is that nominator and denominator quickly become too large to be stored in standard integer formats.