Dividing by zero – how bad is it, really?∗ Takayuki Kihara1 and Arno Pauly2

論文読んでみます；

Dividing by zero – how bad is it, really?∗
Takayuki Kihara1 and Arno Pauly2

1 Department of Mathematics
University of California, Berkeley, United States
kihara@math.berkeley.edu
2 Département d’Informatique
Université Libre de Bruxelles, Belgium
Arno.M.Pauly@gmail.com

Abstract
In computable analysis testing a real number for being zero is a fundamental example of a noncomputable
task. This causes problems for division: We cannot ensure that the number we want
to divide by is not zero. In many cases, any real number would be an acceptable outcome if the
divisor is zero - but even this cannot be done in a computable way.
In this note we investigate the strength of the computational problem Robust division: Given
a pair of real numbers, the first not greater than the other, output their quotient if well-defined
and any real number else. The formal framework is provided by Weihrauch reducibility. One
particular result is that having later calls to the problem depending on the outcomes of earlier
ones is strictly more powerful than performing all calls concurrently. However, having a nesting
depths of two already provides the full power. This solves an open problem raised at a recent
Dagstuhl meeting on Weihrauch reducibility.
As application for Robust division, we show that it suffices to execute Gaussian elimination.
1998 ACM Subject Classification F.2.1 Numerical Algorithms and Problems
Keywords and phrases computable analysis; Weihrauch reducibility; recursion theory; linear
algebra
Digital Object Identifier 10.4230/LIPIcs...
1 Introduction
We cannot divide by zero! is probably the first mathematical impossibility statement everyone
encounters. In the setting we see it first, arithmetic of concrete integers, this does not cause
any problems: Since it is obvious whether some number is zero or not, we simply refrain from
attempting it – and the multiplicative absorption of 0 ensures that we have no reason for an
attempt anyway. As our mathematical world expands to include more kinds of numbers, and
in particular variables, we may have to introduce case distinctions at times in order to avoid
this problem1
.
In most practical situations, this may seem unproblematic. However, a fundamental
observation by Brouwer in the early development of constructive mathematics was that we
cannot in general decide whether a real number is zero or not. Thus, a case distinction based
∗ The first author was partially supported by a Grant-in-Aid for JSPS fellows. The second author was
partially supported by the ERC inVEST (279499) project.
1 Forgetting about these cases has probably caused a lot of anguish to pupils learning the outcome of
their exams.
© Takayuki Kihara and Arno Pauly;
licensed under Creative Commons License CC-BY
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
arXiv:1606.04126v1 [cs.LO] 13 Jun 2016
XX:2 Dividing by zero – how bad is it, really?
on whether our intended denominator is zero or not is not constructive. In a constructive
setting, we can only divide by a number we know to be different from zero.
To consider a concrete example where we might want to divide by a number that could
be zero, consider a, b ∈ R with 0 ≤ a ≤ b, and the linear equation a = bx. We know that
there is a solution x0 ∈ [0, 1]: If b 6= 0, then x0 := a
b
, otherwise b = a = 0, and any x works.
We see that we do not actually care about whether b = 0 or not, and we do not even need
any particular outcome of a misguided attempt to calculate 0
0
– any number would do.
Unfortunately, the algorithm to divide a real number a by a real number b starts with
searching for a rational number bounding b away from 0. If no such number exists, there will
be no output at all, rather than some arbitrary number. The robust division we would like
to employ to solve linear equations as above is not actually computable.
In this note, we study the extent of non-computability of robust division in the formal
setting of Weihrauch reducibility. Some results had already been obtained in [16]. We will
recall that robust division lies strictly in between the traditional non-constructive principles
LLPO and LPO and some other basic properties. Our concern then is with the question how
multiple uses of robust division interact. We show that sequential uses of robust division
cannot be reduced to parallel uses – however, it suffices to have a nesting depths of 2.
In [16], finding the solution to systems of linear inequalities via a modified Fourier-Motzkin
elimination, and finding Nash equilibria in bimatrix games were explored as applications of
robust division. Here, we shall consider Gaussian elimination as additional example.


Gaussian Elimination
Most work on algorithms in linear algebra assumes equality to be decidable, and is thus
applicable to computability over the rational or algebraic numbers, but not to computability
over the real numbers. In the latter setting, computability of some basic questions (rank,
eigenvectors,. . . ) was studied in [29], with some additional results in [28, 10]. Here, we shall
consider LU-decomposition and Gaussian elimination.
Gaussian elimination is one of the basic algorithms in linear algebra, used in particular
to compute the LU-decomposition of matrices. The goal is to transform a given matrix into
row echelon form by means of swapping rows (and maybe columns) and adding multiples of
one row to another. Sometimes the leading non-zero coefficients in each row are required
to be 1, however, as this is easily seen to require equality testing, we shall not include this
requirement.
I Definition 26. LU-DecompP,Q takes as input a matrix A, and outputs permutation
matrices P, Q, a matrix U in upper echelon form and a matrix L in lower echelon form
with all diagonal elements being 1 such that P AQ = LU. By LU-DecompQ we denote the
extension where P is required to be the identity matrix.
I Theorem 27. LU-DecompP,Q ≡W rDiv∗
and rDiv∗ ≤W LU-DecompQ ≤W rDiv∗
? rDiv∗
.
The proof of the preceding theorem follows in form of some lemmata. We point out
that the upper bounds are proven via variants of Gaussian elimination. In the case of
LU-DecompP,Q and its matching lower bound, this shows that Gaussian elimination exhibits
no more incomputability than inherent in the problem it solves. It is consistent with the
classifications that the extra freedom in choosing the pivot elements in solving LU-DecompP,Q
compared to solving LU-DecompQ makes the problem less incomputable. Resolving the
precise degree of LU-DecompQ seems to be beyond the reach of our current methods though.
I Lemma 28. LU-DecompP,Q ≡W LU-Decomp∗
P,Q and LU-DecompQ ≡W LU-Decomp∗
Q.
T. Kihara & A. Pauly XX:13
Proof. An LU-decomposition of
A 0
0 B

gives rise to LU-decompositions of both A and
B. J
I Lemma 29. LU-DecompP,Q ≤W rDiv∗
.
Proof. Initially, we rearrange all the matrix elements such that at each step the pivot element
chosen has the largest absolute value amongst the remaining elements, and obtain their
signs. This can be achieved by C{0,...,k} for suitable k. Then we can compute all the relevant
divisions simultaneously, using some rDivl
. Corollary 22 then shows that this reduces to
rDiv∗
. J
I Lemma 30. LU-DecompQ ≤W rDiv∗
? rDiv∗
.
Proof. Given some real matrix (aij )i≤n,j≤m we can use C{0,...,n−1} to pick some i0 such that
|ai0,1| = maxi≤n |ai,1|, and permute the rows to move the i0-th row to the top. We can use
C
n
{0,1}
to figure out for each i whether |ai,1| is non-negative or non-positive. For each i =6 i0
we compute rDiv(|ai,1|, |ai0,1|), pick the sign depending on the putative signs on ai,1 and
ai0,1 and then subtract the corresponding multiple of the i0-th row from the i-th row. By
choice of i0, either all ai,1 are 0 anyway, or ai0,1 6= 0 – in both cases, this ensures that in all
rows but the i0-th the first entry is zero after the operation.
The procedure so far made use of rDivn−1
?

C{0,...,n−1} × C
n
{0,1}

.
After the first round, the now first row is fixed. Amongst the remaining ones, we pick one
with the largest absolute value in the second column (using C{0,...,n−2}), determine the signs
of entries in the second column (using C
n−2
{0,1}
) and again use rDiv to compute the coefficients
for subtracting the second row from the lower ones.
This is repeated until each row has been dealt with. Overall, we use n − 1 rounds, so
the procedure is reducible to h
rDivn−1
?

C{0,...,n−1} × C
n
{0,1}
i(n)
. By repeated application
of Corollaries 22,23 this reduces to AoUCk
[0,1] ? AoUCk
[0,1] for sufficiently big k (depending
effectively on n). J
I Lemma 31. rDiv ≤W LU-DecompP,Q.
Proof. We consider the computable function B : [0, 1] → R
2×2 of matrices defined via:
B(ε) = exp(−ε
−2
)

cos(ε
−1
) sin(ε
−1
)
− sin(ε
−1
) cos(ε
−1
)

for ε > 0 B(0) =
0 0
0 0
This is based on a counterexample due to Rellich (cmp. [14, II.5.3], [29, Example 18]). If
ε = 0 6 , then the lower-left corner of L in an LU-decomposition of B(ε) will be one of tan ε
−1
,
cot ε
−1 or − cot ε
−1
. The relevant case can be obtained from P and Q. As arctan and arccot
are total, we can apply the relevant inverse even if ε = 0, and thus the lower-left corner of L
is an arbitrary real number. Let x
0
ε be the result, and xε = max{0, min{1, x0
ε}}.
We want to show that AoUC[0,1] ≤W GaussElim (which is equivalent to the claim by
Proposition 8). Given A ∈ dom(AoUC[0,1]), we show how to compute some ε ∈ [0, 1] such
that xε ∈ A. As long as A = [0, 1] is consistent with our knowledge of the input, we specify
that ε ∈ [0, 2
−t
] for smaller and smaller t ∈ N. If we learn at time t that A 6= [0, 1], we
compute y such that A = {y} and choose k ∈ N such that (2kπ)
−k ≤ 2
−t
. We can then
specify ε = (2kπ+y)
−1
. But now xε = y. If A = [0, 1], then xε ∈ A anyway by definition. Jhttp://arxiv.org/pdf/1606.04126.pdf

\documentclass[12pt]{article}
\usepackage{latexsym,amsmath,amssymb,amsfonts,amstext,amsthm}
\numberwithin{equation}{section}
\begin{document}
\title{\bf Announcement 300: New challenges on the division by zero z/0=0\\
(2016.05.22)}
\author{{\it Institute of Reproducing Kernels}\\
Kawauchi-cho, 5-1648-16,\\
Kiryu 376-0041, Japan\\

%\date{\today}
\maketitle
{\bf Abstract: } In this announcement, for its importance we would like to state the
situation on the division by zero and propose basic new challenges.

\bigskip
\section{Introduction}
%\label{sect1}
By a {\bf natural extension} of the fractions
\begin{equation}
\frac{b}{a}
\end{equation}
for any complex numbers $a$ and $b$, we found the simple and beautiful result, for any complex number $b$
\begin{equation}
\frac{b}{0}=0, 
\end{equation}
incidentally in \cite{s} by the Tikhonov regularization for the Hadamard product inversions for matrices and we discussed their properties and gave several physical interpretations on the general fractions in \cite{kmsy} for the case of real numbers.

The division by zero has a long and mysterious story over the world (see, for example, Google site with the division by zero) with its physical viewpoints since the document of zero in India on AD 628, however,
Sin-Ei Takahasi (\cite{kmsy}) established a simple and decisive interpretation (1.2) by analyzing the extensions of fractions and by showing the complete characterization for the property (1.2):

\bigskip

{\bf Proposition 1. }{\it Let F be a function from ${\bf C }\times {\bf C }$ to ${\bf C }$ satisfying
$$
F (b, a)F (c, d)= F (bc, ad) 
$$ 
for all
$$
a, b, c, d \in {\bf C }
$$
and 
$$
F (b, a) = \frac {b}{a }, \quad a, b \in {\bf C }, a \ne 0.
$$
Then, we obtain, for any $b \in {\bf C } $ 
$$
F (b, 0) = 0.
$$
}

Note that the complete proof of this proposition is simply given by 2 or 3 lines.

\medskip
We thus should consider, for any complex number $b$, as (1.2); 
that is, for the mapping
\begin{equation}
w = \frac{1}{z},
\end{equation}
the image of $z=0$ is $w=0$ ({\bf should be defined}). This fact seems to be a curious one in connection with our well-established popular image for the point at infinity on the Riemann sphere. Therefore, the division by zero will give great impacts to complex analysis and to our ideas for the space and universe.

However, the division by zero (1.2) is now clear, indeed, for the introduction of (1.2), we have several independent approaches as in:

\medskip
1) by the generalization of the fractions by the Tikhonov regularization or by the Moore-Penrose generalized inverse, 

\medskip
2) by the intuitive meaning of the fractions (division) by H. Michiwaki,

\medskip
3) by the unique extension of the fractions by S. Takahasi, as in the above,

\medskip
4) by the extension of the fundamental function $W = 1/z$ from ${\bf C} \setminus \{0\}$ into ${\bf C}$ such that $W =1/z$ is a one to one and onto mapping from $ {\bf C} \setminus \{0\} $ onto ${\bf C} \setminus \{0\}$ and the division by zero $1/0=0$ is a one to one and onto mapping extension of the function $W =1/z $ from ${\bf C}$ onto ${\bf C}$, 

\medskip
and

\medskip

5) by considering the values of functions with the mean values of functions.
\medskip

Furthermore, in (\cite{msy}) we gave the results in order to show the reality of the division by zero in our world:

\medskip

\medskip
A) a field structure containing the division by zero --- the Yamada field ${\bf Y}$,

\medskip
B) by the gradient of the $y$ axis on the $(x,y)$ plane --- $\tan \frac{\pi}{2} =0$,
\medskip

C) by the reflection $W =1/\overline{z}$ of $W= z$ with respect to the unit circle with center at the origin on the complex $z$ plane --- the reflection point of zero is zero,
\medskip

and
\medskip

D) by considering rotation of a right circular cone having some very interesting
phenomenon from some practical and physical problem.

\medskip

In (\cite{mos}), many division by zero results in Euclidean spaces are given and the basic idea at the point at infinity should be changed. In (\cite{ms}), we gave beautiful geometrical interpretations of determinants from the viewpoint of the division by zero. The results show that the division by zero is our basic and elementary mathematics in our world.

\medskip

See J. A. Bergstra, Y. Hirshfeld and J. V. Tucker \cite{bht} for the relationship between fields and the division by zero, and the importance of the division by zero for computer science. It seems that the relationship of the division by zero and field structures are abstract in their paper.

Meanwhile, J. P. Barukcic and I. Barukcic (\cite{bb}) discussed recently the relation between the divisions $0/0$, $1/0$ and special relative theory of Einstein. However, their logic seems to be curious and their results contradict with ours.

Furthermore, T. S. Reis and J.A.D.W. Anderson (\cite{ra,ra2}) extend the system of the real numbers by introducing an ideal number for the division by zero $0/0$. 

Meanwhile, we should refer to up-to-date information:

{\it Riemann Hypothesis Addendum - Breakthrough

Kurt Arbenz
https://www.researchgate.net/publication/272022137 Riemann Hypothesis Addendum - Breakthrough.}

\medskip

Here, we recall Albert Einstein's words on mathematics:
Blackholes are where God divided by zero.
I don't believe in mathematics.
George Gamow (1904-1968) Russian-born American nuclear physicist and cosmologist remarked that "it is well known to students of high school algebra" that division by zero is not valid; and Einstein admitted it as {\bf the biggest blunder of his life} [1]：
1. Gamow, G., My World Line (Viking, New York). p 44, 1970.

For our ideas on the division by zero, see the survey style announcements 179,185,237,246,247,250 and 252 of the Institute of Reproducing Kernels (\cite{ann179,ann185,ann237,ann246,ann247,ann250,ann252,ann293}).

\section{On mathematics}
Apparently, the division by zero is a great missing in our mathematics and the result (1.2) is definitely determined as our basic mathematics, as we see from Proposition 1. Note its very general assumptions and many fundamental evidences in our world in (\cite{kmsy,msy,mos}). The results will give great impacts on Euclidean spaces, analytic geometry, calculus, differential equations, complex analysis and physical problems. See our announcements for the details.

The mysterious history of the division by zero over one thousand years is a great shame of mathematicians and human race on the world history, like the Ptolemaic system (geocentric theory). The division by zero will become a typical symbol of foolish human race with long and unceasing struggles. Future people will realize this fact as a definite common sense.

We should check and fill our mathematics, globally and beautifully, from the viewpoint of the division by zero. Our mathematics will be more perfect and beautiful, and will give great impacts to our basic ideas on the universe.

\section{Albert Einstein's biggest blunder}
The division by zero is directly related to the Einstein's theory and various 
physical problems
containing the division by zero. Now we should check the theory and the problems by the concept of the RIGHT and DEFINITE division by zero. Now is the best time since 100 years from Albert Einstein. It seems that the background knowledge is timely fruitful.

\section{Computer systems}
The above Professors listed are wishing the contributions in order to avoid the zero division trouble in computers. Now, we should arrange new computer systems in order not to meet the division by zero trouble in computer systems.

\section{General ideas on the universe}
The division by zero may be related to religion, philosophy and the ideas on the universe, and it will creat a new world. Look the new world.

\bigskip

We are standing on a new generation and in front of the new world, as in the discovery of the Americas.

\bigskip

\bibliographystyle{plain}
\begin{thebibliography}{10}

\bibitem{bb}
J. P. Barukcic and I. Barukcic, Anti Aristotle—The Division of Zero by Zero. Journal of Applied Mathematics and Physics, {\bf 4}(2016), 749-761.
doi: 10.4236/jamp.2016.44085.

\bibitem{bht}
J. A. Bergstra, Y. Hirshfeld and J. V. Tucker,
Meadows and the equational specification of division (arXiv:0901.0823v1[math.RA] 7 Jan 2009).

\bibitem{cs}
L. P. Castro and S. Saitoh, Fractional functions and their representations, Complex Anal. Oper. Theory {\bf7} (2013), no. 4, 1049-1063. 

\bibitem{kmsy}
M. Kuroda, H. Michiwaki, S. Saitoh, and M. Yamane,
New meanings of the division by zero and interpretations on $100/0=0$ and on $0/0=0$,
Int. J. Appl. Math. {\bf 27} (2014), no 2, pp. 191-198, DOI: 10.12732/ijam.v27i2.9.

\bibitem{ms}
T. Matsuura and S. Saitoh,
Matrices and division by zero $z/0=0$,
Linear Algebra \& Matrix Theory (ALAMT)(to appear).

\bibitem{msy}
H. Michiwaki, S. Saitoh, and M.Yamada, 
Reality of the division by zero $z/0=0$. IJAPM International J. of Applied Physics and Math. {\bf 6}(2015), 1--8. http://www.ijapm.org/show-63-504-1.html

\bibitem{mos}
H. Michiwaki, H. Okumura, and S. Saitoh,
Division by Zero $z/0 = 0$ in Euclidean Spaces.
International Journal of Mathematics and Computation 
(in press).

\bibitem{ra}
T. S. Reis and J.A.D.W. Anderson,
Transdifferential and Transintegral Calculus,
Proceedings of the World Congress on Engineering and Computer Science 2014 Vol I
WCECS 2014, 22-24 October, 2014, San Francisco, USA

\bibitem{ra2}
T. S. Reis and J.A.D.W. Anderson,
Transreal Calculus, 
IAENG International J. of Applied Math., {\bf 45}(2015): IJAM 45 1 06.

\bibitem{s}
S. Saitoh, Generalized inversions of Hadamard and tensor products for matrices, Advances in Linear Algebra \& Matrix Theory. {\bf 4} (2014), no. 2, 87--95. http://www.scirp.org/journal/ALAMT/ 

\bibitem{ttk}
S.-E. Takahasi, M. Tsukada and Y. Kobayashi, Classification of continuous fractional binary operations on the real and complex fields, Tokyo Journal of Mathematics, {\bf 38}(2015), no. 2, 369-380.

\bibitem{ann179}
Announcement 179 (2014.8.30): Division by zero is clear as z/0=0 and it is fundamental in mathematics.

\bibitem{ann185}
Announcement 185 (2014.10.22): The importance of the division by zero $z/0=0$.

\bibitem{ann237}
Announcement 237 (2015.6.18): A reality of the division by zero $z/0=0$ by geometrical optics.

\bibitem{ann246}
Announcement 246 (2015.9.17): An interpretation of the division by zero $1/0=0$ by the gradients of lines.

\bibitem{ann247}
Announcement 247 (2015.9.22): The gradient of y-axis is zero and $\tan (\pi/2) =0$ by the division by zero $1/0=0$.

\bibitem{ann250}
Announcement 250 (2015.10.20): What are numbers? - the Yamada field containing the division by zero $z/0=0$.

\bibitem{ann252}
Announcement 252 (2015.11.1): Circles and
curvature - an interpretation by Mr.
Hiroshi Michiwaki of the division by
zero $r/0 = 0$.

\bibitem{ann281}
Announcement 281(2016.2.1): The importance of the division by zero $z/0=0$.

\bibitem{ann282}
Announcement 282(2016.2.2): The Division by Zero $z/0=0$ on the Second Birthday.

\bibitem{ann293}
Announcement 293(2016.3.27): Parallel lines on the Euclidean plane from the viewpoint of division by zero 1/0=0.

\end{thebibliography}

\end{document}