MATHEMATICS

• Views and branches - numbers, shapes, arithmethic, calculus, reasoning, ...
• High level overviews
• Associations
• Universities
• Problem hardness and complexity
• Famous solved problems
• Proofs
• Arithmetic - modular arithmethic, p-adic numbers
• Algebra - set, group, ring, field, polynomial, elliptic curve, pairing, ...
• Logic
• Reasoning
• Logic intro
• Set theory and Z
• Tools
• Process calculus
• Finite State Machines
• Proposition logic - SMT, SAT
• FOL
• Subjective logic
• Deontic logic
• Number theory
• Graphs
• Transformations
• Linear Programming
• Information and computation
• Tools
• NIST
• Python/SageMath
• Regex
• sed
• Mathworld - Matlab
• Other
• Humour

Views and branches

Views

• Arithmetic (Egypt - numbers), geometry (Greece - shape), calculus (Europe - 17th century - motion, change, space).
• Counting (arithmetic - number theory - primes), reasoning and communication (logic, Venn diagrams, set theory, grammar), motion and change (series, functions, calculus, differentials, integration, analytic number theory), shape (geometry), symmetry (symmetry groups, sphere packing), position (topology, surfaces, knots, elliptic curves)
• mathematica (...)

Branches of abstract algebra

• Abstract algebra (how to specify sets, groups, rings, fields, how to compute with their elements)
• Abstract Algebra - great overview + Sage exercises, covering:
• The Integers
• Groups
• Cyclic Groups
• Permutation Groups
• Cosets and Lagrange’s Theorem
• Introduction to Cryptography
• Algebraic Coding Theory
• Isomorphisms
• Normal Subgroups and Factor Groups
• Homomorphisms
• Matrix Groups and Symmetry
• The Structure of Groups
• Group Actions
• The Sylow Theorems
• Rings
• Polynomials
• Integral Domains
• Lattices and Boolean Algebras
• Vector Spaces
• Fields
• Finite Fields
• Galois Theory

High level

Overview

• Karl Popper -
  • 'The logic of scientific discovery'
  • Also: 'We should therefore claim, in the name of tolerance, the right not to tolerate the intolerant.'

• Tricki.org - a Wiki-style site that is intended to develop into a large store of useful mathematical problem-solving techniques
• US NIST DLMF - Digital Library of Mathematical Functions
• US NIST DADS - Dictionary of Algorithms and Data Structures
• Encyclopedia-of-math (Springer, in cooperation with the European Mathematical Society)
• European Mathematical Society
• zbMath (Zentralblatt MATH) - books, authors, classification, (related to European Mathematical Society)
• Wikipedia's Mathematics portal

Associations

• UK - Royal Society - journals/collections/books eg Newton
• EU - EMIS - European Mathemathical Information Service
• US - MAA
• US - AMS

Universities

• Be - Ugent
• Be - KU-Leuven
• DE - Mannheim
• NL - EIDMA - Euler Institute for Discrete Mathematics and its Applications - Henk van Tilborg, Lenstra, ...
• US - Number Theory Web
• US - Berkeley Math
• US - Stanford - Statistics
• IL - Haifa - robotics
• IL - Weizmann
• IL - Weizmann's links to Ben-Gurion, Technion, Haifa, ...

Mathematics Subject Classification

• MSC

Problem hardness and complexity

• Oded Goldreich - Weizman - complexity, proofs, cryptography

P, NP, NP-complete, NP-hard

• P versus NP - Wikipedia
• The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

P for Polynomial time

• Polynomial time - Wikipedia
• An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, that is, T(n) = O(n^k) for some positive constant k.
• Problems for which a deterministic polynomial-time algorithm exists belong to the complexity class P.
• Cobham's thesis states that polynomial time is a synonym for "tractable", "feasible", "efficient", or "fast".

NP for Non-deterministic Polynomial time

• Non-deterministic Polynomial time - Wikipedia
• Have proofs verifiable in polynomial time.
• It is easy to see that the complexity class P (all problems solvable, deterministically, in polynomial time) is contained in NP (problems where solutions can be verified in polynomial time), because if a problem is solvable in polynomial time, then a solution is also verifiable in polynomial time by simply solving the problem.
• NP-completeness - short for "nondeterministic polynomial-time complete - Wikipedia
• Although a solution to an NP-complete problem can be verified "quickly", there is no known way to find a solution quickly.
• NP-hardness - short for "nondeterministic polynomial-time complete - Wikipedia
• is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP".
• A simple example of an NP-hard problem is the subset sum problem.
• Subset Sum Problem - Wikipedia
• There is a multiset S of integers and a target-sum T, and the question is to decide whether any subset of the integers sum to precisely T.
• The problem is known to be NP-hard. Moreover, some restricted variants of it are NP-complete.

Computational complexity

• Computational complexity - Wikipedia
• Computational complexity theory - Wikipedia
• Complexity classes
• Deterministic time/space: f(n), log(n), poly(n), exponential i.e. 2^poly(n)
• Non-deterministic time/space: non-deterministic version of f(n), log(n), poly(n), exponential i.e. 2^poly(n)
• Complexity classes - overview - Wikipedia
• Computational complexity of mathematical operations - Wikipedia

Time complexity

• Time complexity - Wikipedia
• Describes the amount of computer time it takes to run an algorithm.
• Commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform.
• Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.
• Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size.

• One needs to determine how long the algorithm takes, in terms of the size of its input.
• Also, one needs to consider how fast a function grows with the input size, the rate of growth of the running time.

• Asymptotic notation - Khan Academy
• big-Θ (big-theta) notation expresses that a running time, once n gets large enough, the running time is at least k₁⋅n and at most k₂⋅n for some constants k₁ and k₂.
• big-Ω (big-omega) notation expresses that an algorithm takes at least a certain amount of time, without providing an upper bound.
• Big-Ω notation is used for asymptotic lower bounds, it bounds the growth of the running time from below for large enough input sizes.
• big-O notation, typically O(n), O(log n), O(n^a), etc., where n is the size in units of bits needed to represent the input.
• Algorithmic complexities can be classified according to the type of function appearing in the big O notation. For example, an algorithm with time complexity O(n) is a linear time algorithm and an algorithm with time complexity O(n^a) for some constant a > 1 is a polynomial time algorithm.
• Big O notation - Wikipedia

Circuit complexity

• Circuit complexity - Wikipedia
• branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them.
• A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits

Famous solved problems

• Fermat's last theorem - Wikipedia
• Wiles proof of Fermat's last theorem - Wikipedia

Proofs

Basics

• Proof - an overloaded term - Wikipedia
• Propositional proof - 'truth' - Wikipedia
• Formal proof - Wikipedia - a finite sequence of sentences (called well-formed formulas in the case of a formal language), each of which is an axiom, an assumption, or follows from the preceding sentences in the sequence by a rule of inference.
• Proof complexity - Wikipedia - concerned with proving proof-length lower and upper bounds in various propositional proof systems - connects to SAT solvers

Soundness and completeness

Interactive Proofs

• that the verifier accepts a correct proof, and
• rejects an incorrect assertion with a probability of at least 2/3.
• ... however, one usually tries to obtain a probability less than 2^-k where k is the security parameter...
• ...a way to achieve this 'security amplification' is to take a protocol with 1/3 error probability, run it O(k) times and accept/reject by majority vote

Probabilistically Checkable Proofs (PCP)

• PCP - Wikipedia
• A type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm is then required to accept correct proofs and reject incorrect proofs with very high probability.
• A standard proof (or certificate), as used in the verifier-based definition of the complexity class NP, also satisfies these requirements, since the checking procedure deterministically reads the whole proof, always accepts correct proofs and rejects incorrect proofs.
• However, what makes them interesting is the existence of probabilistically checkable proofs that can be checked by reading only a few bits of the proof using randomness in an essential way.

Arithmetic

Arithmethic

• Arithmetic - Wikipedia

Modular arithmetic

• Modular arithmetic developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, 1801
• Given an integer n > 1, called a modulus, two integers a and b are said to be congruent modulo n, if n is a divisor of their difference (that is, if there is an integer k such that a − b = kn).
• The modulo operation: the notation b mod n (without parentheses) refers to the modulo operation. Indeed, b mod n denotes the unique integer a such that 0 ≤ a < n and a ≡ b (mod n)(that is, the remainder of b when divided by n
• The congruence equation: the notation a ≡ b (mod n), where the parentheses mean that (mod n) applies to the entire equation, not just to the right-hand side (here, b).
• Given an integer n > 1, called a modulus, a ≡ b (mod n) if n is a divisor of their difference (if there is an integer k such that a − b = k.n)
• Reduction: 9 (mod 2) ≡ 1 (mod 2) (there is an integer k(=4) such that 9-1 = k.2
• Reduction: 9 (mod 2) ≡ 1 (mod 2) (there is an integer k(=4) such that 9-1 = k.2
• Reduction: 8 (mod 2) ≡ 0 (mod 2) (there is an integer k(=4) such that 8-0 = k.2
• Planetcalc - all kinds of calculators including for modular arithmethic
• Observation: 7-5=2, 5-7=-2 7 ≡ 5 (mod 2) because 7-5=2, (2 mod 2) = -4 | 2
• In modulus 12, one can assert that 38 ≡ 14 (mod 12) because 38 − 14 = 24 (a multiple of 12, with k=2). Alternatively, 14 ≡ 38 (mod 12) because 14 − 38 = -24 (also a multiple of 12, with k=-2).
• Another way to express this is to say that both 38 and 14 have the same remainder 2, when divided by 12.
• More examples: 8 mod 4 ≡ 0, 7 mod 2 ≡ 1
• The definition of congruence also applies to negative values. For example:
• 2 ≡ − 3 (mod 5) because -3 -2 | 5 (the notation (mod 5) at the end of the expression means mod 5 applies to both sides of the equation)
• − 8 ≡ 7 (mod 5) because 7 - (-8) = 15 | 5
• − 3 ≡ − 8 (mod 5) because -8 - (-3) = 5 | 5
• 1 ≡ − 3 (mod 2) because -3 -1 = -4 | 2
• 330 ≡ -1 (mod 331) because -1 - 330 = -331 | 331
• Fermat's little theorem and quite a few other calculators
• If p is a prime number, then for any integer a, the number a^{p − a} is an integer multiple of p.
• Expressed otherwise: a^p ≡ a mod p
• Also, if a is not divisible by p, Fermat's little theorem is equivalent to the statement that a^{p − 1}− 1 is an integer multiple of p.
• Expressed otherwise: a^p-1 ≡ 1 mod p
• Root of unity modulo n - Wikipedia and quite a few other calculators
• A k^th root of unity modulo n for positive integers k, n ≥ 2, is a root of unity in the ring of integers modulo n; that is, a solution x to the equation (or congruence) x k ≡ 1 ( mod n ).
• If k is the smallest such exponent for x, then x is called a primitive k^th root of unity modulo n.
• Modular arithmetic calculator and quite a few other calculators

p-adic numbers

• p-adic number - Wikipedia
• the p-adic number system for any prime number p extends the ordinary arithmetic of the rational numbers in a different way from the extension of the rational number system to the real and complex number systems.
• The extension is achieved by an alternative interpretation of the concept of "closeness" or absolute value. In particular, two p-adic numbers are considered to be close when their difference is divisible by a high power of p: the higher the power, the closer they are.
• This property enables p-adic numbers to encode congruence information in a way that turns out to have powerful applications in number theory – including, for example, in the famous proof of Fermat's Last Theorem by Andrew Wiles
• p-adic valuation - Wikipedia
• the p-adic valuation or p-adic order of an integer n is the exponent of the highest power of the prime number p that divides n. It is denoted ν_p(n) Equivalently, ν_p(n) is the exponent to which p in the prime factorization of n.

Algebra

• Algebra - Wikipedia
• Elementary algebra deals with the manipulation of variables such as x as if they were numbers.
• Linear algebra, which deals with linear equations and linear mappings, is used for modern presentations of geometry, and has many practical applications (weather forecasting ...).
• Abstract algebra is the name given to the study of algebraic structures such as groups, rings, and fields, see below
• Abstract Algebra - great overview + Sage exercises

Abstract algebra

Sets and cosets

• Set - Wikipedia
• Set Theory - Wikipedia
• Coset - Wikipedia

Groups

• Group - is a set and an operation that combines any two elements of the set to produce a third element of the set, in such a way that the operation is associative, an identity element exists and every element has an inverse
• Otherwise said: Group G is a set with 1 binary operation * such that following properties holds: * is associative, there is an identity element, each element has an inverse element
• If a * b = b * a then the group is called abelian or commutative
• If there exists a generator g such that for any element b there is an integer j such that g^j = b then the group is cyclic
• The number of elements in a finite group is called its order, |G|
• The subgroup of G consisting of all powers of the element a is called the subgroup generated by a, denoted by bracket a bracket
• And bracket a bracket is of finite order k if is k is the least positive integer such that a^k = e, the identity element
• Example: the integers together with the addition operation form a group.

Rings

• Ring R - set with 2 binary operations (+ and *) such that R is abelian with respect to +, * is associative, and + and * are distributive
• If there is a multiplicative identity the ring is called a ring with identity
• A ring is called commutative if * is commutative
• A ring is called an integral domain if it is a commutative ring with identiy e ¬ = 0 in which ab=0 implies a=0 or b=0
• A ring is called a diision ring if the nonzero elemnts form a group under *
• A commutative division ring is called a field
• Example: the four common rings: the integers Z_n, the rationals, the reals, the complex numbers

Fields

• Set F with 2 binary operations (+ and *)
• Has two distinguished elements: zero element 0 and identity element e such that e ¬ = 0
• Is an abelian group with regard to + with 0 as identity element
• The elements of F that are ¬ = 0 form an abelian group with regard to *, with e as identity element
• The distributive laws hold on + and *
• Example: Z_p is a finite field, Z_p = {0,1,...,p-1}

• Root of unity - Wikipedia
• Any complex number that yields 1 when raised to some positive integer power n.
• Can be defined in any field.
• If the characteristic of the field is zero, the roots are complex numbers that are also algebraic integers.
• The characteristic of a ring R, often denoted char(R), is defined to be the smallest number of times one must use the ring's multiplicative identity (1) in a sum to get the additive identity (0). If this sum never reaches the additive identity the ring is said to have characteristic zero.
• For fields with a positive characteristic, the roots belong to a finite field, and, conversely, every nonzero element of a finite field is a root of unity.
• Any algebraically closed field contains exactly n nth roots of unity, except when n is a multiple of the (positive) characteristic of the field.

Quadratic residues, Legendre and Jacobi symbols

QR

• QR - Wikipedia integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that x² ≡ q (mod n) - finding x may be hard
• Euler's criterion - Wikipedia
• Is a formula for determining whether an integer is a quadratic residue modulo a prime via a^(p-1)|2 mod p
• Let p be an odd prime and a be an integer coprime to p. Then:
• a^(p-1)|2 ≡ 1 mod p if there is an integer x such that a ≡ x² mod p
• a^(p-1)|2 ≡ -1 mod p otherwise
• Illustration 1: which numbers are squares modulo 17 (quadratic residues modulo 17)? We can manually calculate it as:
• 1² = 1
• 2² = 4
• 3² = 9
• 4² = 16
• 5² = 25 ≡ 8 (mod 17)
• 6² = 36 ≡ 2 (mod 17)
• 7² = 49 ≡ 15 (mod 17)
• 8² = 64 ≡ 13 (mod 17).
• So the set of the quadratic residues modulo 17 is {1,2,4,8,9,13,15,16}.
• Illustration 2: let a = 17. For which primes p is 17 a quadratic residue? We can test prime p's manually given the Eurler formula a^(p-1)|2 mod p.
• Consider p = 3, then 17^{(3 − 1)|2} = 17¹ ≡ 2 ≡ −1 (mod 3), therefore 17 is not a quadratic residue modulo 3.
• Consider p = 13, then 17^{(13 − 1)|2} = 17⁶ ≡ 1 (mod 13), therefore 17 is a quadratic residue modulo 13. As confirmation, note that 17 ≡ 4 (mod 13), and 22 = 4.
• Law of quadratic reciprocity - Wikipedia
• gives conditions for the solvability of quadratic equations modulo prime numbers
• allows to determine whether there is an integer solution for any quadratic equation of the form x² ≡ a mod p for an odd prime p, that is, to determine the "perfect squares" modulo p.

Legendre - prime p and integer a

• Legendre symbol - Wikipedia - defined to proof the law of quadratic reciprocity
• Legendre symbol - prime p and integer a
• Let p be an odd prime number. An integer a is a quadratic residue modulo p if it is congruent to a perfect square modulo p and is a quadratic non-residue modulo p otherwise. The Legendre symbol is a function of a and p defined as
• +1 if a is a QR modulo p and a not ≡ 0 mod p
• -1 if a a quadratic non-residue modulo p
• 0 if a is ≡ 0 mod p

Jacobi - [composite] integer n and integer a

• Jacobi symbol integer n and integer a - (generalisation of Legendre) - Wikipedia - usefull a.o. in primality testing and integer factorisation
• Let n be any positive odd integer n (which may be composite). For any integer a, the Jacobi symbol (a/n) is defined as the product of the Legendre symbols corresponding to the prime factors of n
• +1 if a is a QR modulo p and a not ≡ 0 mod p
• -1 if a a quadratic non-residue modulo p
• 0 if a is ≡ 0 mod p

Polynomials

• Lagrange theorem - Wikipedia

Elliptic curve

• Elliptic curves - Wikipedia
• Using elliptic curves for primality testing - Wikipedia
• Using elliptic curves for factorisation (Lenstra) - Wikipedia

• The traditional way, using the Weierstrass equation: y²= x³+ax+b
• Huff curves,
• Jacobi quartics,
• (twisted) Edwards curves.

EC pairings

Logic

Reasoning

• Inductive reasoning
• A method of reasoning in which the premises are viewed as supplying some evidence, but not full assurance, of the truth of the conclusion.
• It is also described as a method where one's experiences and observations, including what are learned from others, are synthesized to come up with a general truth.
• Many dictionaries define inductive reasoning as the derivation of general principles from specific observations (arguing from specific to general), although there are many inductive arguments that do not have that form
• Conclusions from inductive reasoning are probably, not certain
• Deductive reasoning
• Is the process of reasoning from one or more statements (premises) to reach a logical conclusion.
• Deductive reasoning links premises with conclusions.
• If all premises are true, the terms are clear, and the rules of deductive logic are followed, then the conclusion reached is necessarily true.

Intro and overview

• Alonzo Church - Princeton - lambda calculus - Church-Turing
• Saul Kripke - modal logic, Kripke systems
• Michael Huth
• Alessandro Artale - Modelling - DL
• Peter Smith
- logic, Gödel, LaTeX, ... (Cambridge)
• ASP- Answer Set Programming (ref Victor Witold Marek)
• Victor Witold Marek- Logic

Set theory and Z

Intro

• Wikipedia - set theory- started by George Cantor
• Stanford on set theory
• Stanford on Zermelo-Fraenkel set theory
• Jonathan Jacky - author of The Way of Z
• Jonathan Jacky - Z examples in LaTeX
• Z user group

Z tools

• CZT - Community Z Tools, including LaTeX styles and parsers, typecheckers, etc
• czt-ide - Releases of standalone CZT IDE, based on Eclipse platform. Use it to author, develop and verify Z specifications.
• Download archived version for Windows 64 bits
• czt-ide-updates - Update sites for released CZT Eclipse plugins to be installed in your own Eclipse IDE.
• czt-jedit - Plugins for the jEdit text editor (www.jedit.org) adding support for typesetting Z specifications.
• czt - Standalone CZT library (classic distribution).
• maven - Instructions how to use CZT libraries deployed to Maven Central.
• CZT Z/Eves- Z Eclipse automated theorem prover IDE
• ZTC- Z type checker
• HOL-Z- High Order Logic Z checker - a plug-in for Isabelle/HOL

Tools

Overview

• Formal verification software- overview by David Mentré - legacy

Alloy

• logic = first order logic + relational calculus
• language = syntax for structuring specifications in the logic
• analysis = bounded exhaustive search for counterexample to a claimed property using SAT

• Alloy- MIT website, from Daniel Jackson
• Alloytools - for describing structures and a tool for exploring them. It has been used in a wide range of applications from finding holes in security mechanisms to designing telephone switching networks

Proof assistants

Isabelle (Cambridge/Muenchen)

• Isabelle- generic proof assistant, allows mathematical formulas to be expressed in a formal language and provides tools for proving those formulas in a logical calculus, originally developed at the University of Cambridge and Technische Universität Muenchen
• Isabelle- University of Cambridge website
• Isabelle- Concrete Semantics (how to)

Coq (INRIA)

• Coq-
• Coq implements a program specification and mathematical higher-level language called Gallina, based on a formal language called the Calculus of Inductive Constructions that itself combines both a higher-order logic and a richly-typed functional programming language

Process calculus

• Pi calculus- a process calculus
• Process calculus - e.g. Hoare CSP

Finite State Machines

• FSM - Wikipedia
• NuSMV- Nex Symbolic Model Checker - open source SAT solver for Temporal Logic such as LTL and CTL - a reimplementation and extension of SMV symbolic model checker

Proposition logic, SAT, SMT

• A formula is satisfiable if it is possible to find an interpretation (model) that makes the formula true.
• A formula is valid if all interpretations make the formula true.

SAT

• Satisfiability.org- conference on propositional satisfiability problem (SAT)
• Satlib- benchmark problems, solvers and tools for SAT research

SMT

• By being theory-specific and restricting their language to certain classes of formulas (such as, typically but not exclusively, quantifier-free formulas), these specialized methods can be implemented in solvers that are more efficient in practice than general-purpose theorem provers.
• An SMT instance is a formula in first-order logic, where some function and predicate symbols have additional interpretations, and SMT is the problem of determining whether such a formula is satisfiable.
• SMT - Wikipedia
• SMTLIB- the Satisfiability Module Theories library
• Z3- Satisfiability Modulo Theories (SMT) solver by Microsoft

FOL and predicate logic

Basics

• FOL- Wikipedia
• Predicate calculus, at the Encyclopedia of Mathematics
• Tree Proof Generator (Semantic Tableaux) for propositional or predicate logic, with documentation

Prolog

• SWISH - SWI-Prolog, with notebooks
• SWISH - SWI-Prolog for the Semantic Web, e.g. handling triples
• Learn Prolog Now , Blackburn, Bos and Striegnitz 2001

KIF

• Knowledge Interchange Format - Wikipedia
• Is a computer language designed to enable systems to share and re-use information from knowledge-based systems.
• Similar to frame languages such as KL-One and LOOM but unlike such language its primary role is not intended as a framework for the expression or use of knowledge but rather for the interchange of knowledge between systems.
Has a declarative semantics.Knowledge can be described as objects, functions, relations, and rules.
• It is a formal language, i.e., it can express arbitrary statements in first order logic and can support reasoners that can prove the consistency of a set of KIF statements.
• KIF also supports non-monotonic reasoning.
• Although the original KIF group intended to submit to a formal standards body, that did not occur. A later version called Common Logic has since been developed for submission to ISO and has been approved and published.
• A variant called SUO-KIF is the language in which the Suggested Upper Merged Ontology SUMO) is written.

Subjective logic

• Audun Josan - probabilistic, beliefs-based

Deontic logic

• Stanford - Deontic Logic - addressing what is (im)permissible, obligatory, etc

Other

• GOLD parser eg for BNF

Number theory

Primes

• Yitang Zhang - twin primes conjecture
• Primes is in P
• GIMPS - Great Internet Mersenne Prime Search

Graphs

Intro

• Graph (discrete mathematics) - Wikipedia
• Graph incidence matrix - one column per edge matrix, the sum of each column is equal to 2 because each edge has a vertex connected to each end.
• Graph adjacency matrix - a square matrix whose elements indicate whether pairs of vertices are adjacent or not in the graph.
• Graph operations - Wikipedia
• Graph rewriting/transformation - Wikipedia
• Permutation graph - Wikipedia
• Graph matching - Wikipedia
• is the problem of finding a similarity between graphs
• In computer vision and pattern recognition it is commonly assumed that the comparison is between the data graph and the model graph
• The case of exact graph matching is known as the graph isomorphism problem
• The problem of exact matching of a graph to a part of another graph is called subgraph isomorphism problem
• Graph isomorphism - exact graph matching - Wikipedia
• Graph isomorphism problem - Wikipedia
• is the computational problem of determining whether two finite graphs are isomorphic
• the problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational complexity class NP-intermediate
• useful in ZK-crypto
• A 'matching' or 'independent edge set' (somewhat confusing terminology) - Wikipedia
• A 'matching' is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching.
• Graph vertex cover problem - Wikipedia
• Information System on Graph Classes and their Inclusions - Java
• Graph database - Wikipedia

Graph in ZK

• Cryptolecture 2006 Ryan Williams - Carnegie Mellon University

Transformations

DSP - FFT - wavelets - compression

• DSPguide.com (book/pdf)- Steven W. Smith - Rapidscan / Sentryscope
• MP3 history - Fraunhofer

Matrices

• UK, Imperial College - The Matrix Reference Manual
• US - Florida - Introduction to Matrix Algebra

Information and computation

• Computational Group Theory - GAP language
• www.combinatorics.org
• www.openscience.org - includes math
• MathFAQ
• UK Turnbull - School for Math and Computational Science - MacTutor - History of Mathematics Archive

Linear Programming

• Linear Programming- Wikipedia
• Simplex algorithm- Wikipedia

Tools

NIST

• NIST DADS - Dictionary of Algorithms and Data Structures - includes definitions such as NP etc, as well as algorithms and datastructures
• NIST GAMS - Guide to available mathematical software - including problem taxonomy

Python/SageMath

• iPhython.org
• SageMath on github - development
• SageMath.org - OpenSource Mathematica
• SageMath docs
• Launching SageMath
• Alternative SageMath docs
• Alternative SageMath docs - Jacobi
• List of mathematical functions native to SageMath: - imports
• From a terminal:
  • 'sage' starts a Sage session in a console - a customised version of the IPython shell, importing some functions and classes, further customisation is by editing the $SAGE_ROOT/ipythonrc file.
  • 'sage -n jupyter' starts a Jupyter notebook
• Functionality: supports computation with objects in many different computer algebra systems “under one roof” using a common interface and clean programming language.
• GAP https://www.gap-system.org/ system for computational discrete algebra, emphasis on Computational Group Theory, consisting of a programming language, libraries, objects.
• GAP capabilities
• GAP documentation
• GP/PARI
• Singular
• Maxima
• SageMath Wiki
• SageMath expository from David Joyner - legacy
• SageMath - William Stein - legacy

Regex

• regex - a regular expression is a sequence of characters that define a search pattern
• A regex processor translates a regular expression into an internal representation which can be executed and matched against a string representing the text being searched in.
• Each character in a regular expression is either a metacharacter or a regular character that has a literal meaning. For example, in the regex a., a is a literal character which matches just 'a', while '.' is a metacharacter that matches every character except a newline.
• Basics:
• a matches letter 'a'
• [a-z] matches all lower case letters from 'a' to 'z'
• '.' is a metacharacter that matches every character except a newline
• a vertical bar separates alternatives ('or'), e.g. gr(a|e)y
• Quantifiers: a quantifier after a token (such as a character) or group specifies how often that a preceding element is allowed to occur
• ? indicates zero or one occurrences of the preceding element. For example, colou?r matches both "color" and "colour".
• * indicates zero or more occurrences of the preceding element. For example, ab*c matches "ac", "abc", "abbc", "abbbc", and so on.
• + indicates one or more occurrences of the preceding element. For example, ab+c matches "abc", "abbc", "abbbc", and so on, but not "ac"
• {n} means the preceding item is matched exactly n times.
• Anchors:
• ^The matches any string that starts with The
• end$ matches a string that ends with end
• ^The end$ exact string match (starts and ends with The end)
• roar matches any string that has the text roar in it
• Character classes:
• \d matches a single character that is a digit
• \w matches a word character (alphanumeric character plus underscore)
• \s matches a whitespace character (includes tabs and line breaks)
• \d, \w and \s also present their negations with \D, \W and \S respectively, for example, \D will perform the inverse match with respect to that obtained with \d, so \D matches a single non-digit character
• . matches any character as a wildcard, for example, a.b matches any string that contains an "a", then any other character and then a "b", a.*b matches any string that contains an "a" and a "b" at some later point.
• Escaping: in order to be taken literally, you must escape the characters ^.[$()|*+?{\with a backslash \ as they have special meaning, e.g. \$\d matches a string that has a $ before one digit
• Non-printables: you can match also non-printable characters like tabs \t, new-lines \n, carriage returns \r
• Using \1 to keep part of the pattern: "[a-z][a-z]" will match any two lower case letters. If you wanted to search for lines that had two adjoining identical letters, this pattern wouldn't help. You need to remember what you found, and see if the same pattern occurred again.
  • To mark part of a pattern using "\(" and "\)",
  • To recall the remembered pattern use "\" followed by a single digit.
  Therefore, to search for two identical letters, use "\([a-z]\)\1". You can have 9 different remembered patterns.
• Standards: the IEEE POSIX standard has 3 sets of compliance: BRE (Basic Regular Expressions), ERE (Extended Regular Expressions), and SRE (Simple Regular Expressions) - deprecated
• Regex can be used e.g. in grep or sed, such as 'sed 's/regexp/replacement/g' inputFileName > outputFileName'
• In sed the s stands for substitute, while the g stands for global, which means that all matching occurrences in the line would be replaced.
• The replacement can be literal text or a format string containing the characters & for "entire match" or the special escape sequences \1 through \9 for the nth saved sub-expression
• Regex editor e.g. any https corresponds to /[https\:\/\/]/

sed

• sed - gnu.org page
• sed - wikipedia - basic examples
• Usage: sed SCRIPT INPUTFILE...
• Usage for substitution: sed 's/regexp/replacement/g' inputFileName > outputFileName where
• s represents the substitute command
• g represents the global flag, i.e. replace all occurances found, not only the first one (as by default)
• ...

Mathworld - Matworks - Matlab

• Wolfram's MATHworld - Eric Weisstein's World of Mathematics
• Wolfram's Mathematica
• Wolfram's search engine/solver - Wolfram Alpha
• MathWorks - MATLAB -
• NL - The MathWorks - MATLAB & Toolboxes such as:
• Statistic
• Curve Fitting
• Optimization
• Symbolic Math
• Image Processing
• Signal Processing
• Neural Network
• Filter Design

Other

• imaginary.org- education and open source

Humour

• Glossary of Mathematical Mistakes - one of the funny sides of math
• XKCD - Randall Munroe