<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by kuco23 on Medium]]></title>
        <description><![CDATA[Stories by kuco23 on Medium]]></description>
        <link>https://medium.com/@nseverkar?source=rss-eadd94c100f7------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*3FTO5kgffEkKMk5I2fUPCA.jpeg</url>
            <title>Stories by kuco23 on Medium</title>
            <link>https://medium.com/@nseverkar?source=rss-eadd94c100f7------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 19:51:56 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@nseverkar/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Implementing a decentralized anonymous voting system]]></title>
            <link>https://nseverkar.medium.com/implementing-a-decentralized-anonymous-voting-system-95508280cf39?source=rss-eadd94c100f7------2</link>
            <guid isPermaLink="false">https://medium.com/p/95508280cf39</guid>
            <category><![CDATA[math]]></category>
            <category><![CDATA[smart-contracts]]></category>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[decentralization]]></category>
            <category><![CDATA[mathematics]]></category>
            <dc:creator><![CDATA[kuco23]]></dc:creator>
            <pubDate>Wed, 21 Dec 2022 01:19:53 GMT</pubDate>
            <atom:updated>2022-12-21T13:08:01.720Z</atom:updated>
            <content:encoded><![CDATA[<h4>Using smart contracts and zero-knowledge proofs</h4><p>Recently, there’s been a lot of interest in zero-knowledge (zk) proofs in the crypto space (see <em>Mina</em>, <em>Zcash</em>, <em>Deco</em>). The main reason is they provide a way to introduce anonymity to transparency-based decentralized systems. We’re going to look at one “simple” application of zk-proofs — a smart contract allowing for anonymous voting.</p><p>The voting implementation is on <a href="https://github.com/kuco23/decentralized-anonymous-voting">this</a> repo, with more specific info about the usage in its readme.</p><h3>Zero-knowledge proofs</h3><h4>General idea</h4><p>Intuitively, zk-proofs allow us to prove possession of a solution without revealing it. For example, we can prove that we have a solution to a sudoku puzzle, without revealing any information about the said solution.</p><p>The main idea of how zk-proofs work is they abuse the fact that knowing a solution to a problem gives you superpowers you do not have otherwise.</p><p>Let’s see how we can prove we have a solution to a sudoku puzzle, with an interaction between a prover (us) and a verifier (some skeptical party). We’re going to simplify things and assume no field is required to hold a specific number (so, we’re proving we know how to fill an empty sudoku puzzle).</p><ul><li>First we randomly shuffle the numbers from 1 to 9 in our solution.</li><li>Then we cryptographically seal the shuffled solution and send that to the verifier. Formally, the sealing is done via some <a href="https://en.wikipedia.org/wiki/One-way_function">one-way function</a>.</li><li>The verifier picks two random fields that have to be in the same 3x3 square or on the same line. He sends us his field choices.</li><li>We send the two keys that unlock the two chosen fields of our sealed solution to the verifier.</li><li>Verifier unlocks his chosen two fields and requires that they contain different numbers.</li></ul><p>Ok, so let’s mention that our hidden solution might be wrong in two different places than the ones chosen by the verifier. In that case, our wrong solution isn’t noticed. This is solved by repeating the above interaction (a lot of times), which arbitrarily reduces the probability of the verifier not noticing us not knowing a solution.</p><p>Next, why doesn’t the verifier learn anything about our solution? Let’s think about what he sees. He only ever sees two different numbers, which is what he already expects from a correctly solved sudoku puzzle. He cannot construct a full solution from those partial solution views through multiple interactions, as we each time randomly shuffle the numbers 1,2,…,9. Two different numbers thus carry absolutely no information about our solution, as they are random.</p><h4>Snarks</h4><p>We are going to look at a specific sort of zk-proofs — <em>zk-snarks</em>, which stands for zero-knowledge succinct non-interactive argument of knowledge. Let’s explain all the words separately</p><ul><li>succinct: proofs are short in size and fast to compute,</li><li>non-interactive: the verification of proof requires no interaction between the prover and verifier,</li><li>argument of knowledge: producing such proofs force the prover to know specific values.</li></ul><p>There are numerous models for zk-snark construction, the two most famous being <em>Groth16 </em>and <em>Plonk</em>. Both produce proofs that depend on a given function/program F and prove statements of the form</p><blockquote>for a given public values a and b I know secret values x and y, such that F(a, x) = (b, y).</blockquote><p>So, for example, you could make a function that takes as public input a sudoku puzzle, as private input its missing values and outputs a public value — 1 if the input is a correct solution and 0 otherwise (note that in this case there is no private output <strong>y</strong>).</p><p>Another more common example is that we have a hiding function <strong>H</strong>. Then we can prove we know a secret hidden value <strong>x </strong>such that for a given public <strong>y</strong> it produces <strong>H(x) = y</strong>. This doesn’t have to be the end though as <strong>x</strong> can be used in further proving. This notion of proving things about hidden values is the basis for many (most?) zk-snark applications.</p><p>One limitation of the functions describing the problems is that they have to be expressed as <em>arithmetic circuits</em>.</p><h4>Arithmetic circuits</h4><p>Because models for zk-snark construction are very mathematical in nature, the problems also have to be described mathematically. Arithmetic circuits describe a problem through enforcing arithmetic (+ and •) connections between defined memory slots (you can imagine them as nodes in a graph). So, each slot has to be either</p><ul><li>a sum of two other slots,</li><li>a product of two other slots.</li></ul><p>Luckily we don’t have to construct raw arithmetic circuits but can describe them via a programming language <em>circom</em>. Check the docs <a href="https://docs.circom.io/">here</a> if you want to learn more about circuit construction via circom. Here I’ll just give a simple example on how to construct a circuit that proves for a polynomial</p><blockquote>p(x) = x⁴ + x³ + x² + 3x + 2</blockquote><p>and a given element <strong>y</strong> the knowledge of input <strong>x</strong> such that <strong>p(x) = y</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/570/1*RzjbfYJKuco2HULBM_iQJw.png" /><figcaption>Circuit of a proof of knowledge of preimage of polynomial <strong>p(x)</strong></figcaption></figure><h4>Practical proof construction</h4><p>This section is for people who want to learn how to concretely construct zk-snarks via a couple of programming tools. Note that once you create your circom circuit, the procedure to construct a zk-snark is algorithmic.</p><p>Using circom’s cli app you can compile your circom circuit description to get a file with the extension .r1cs and another with the extension .wasm, using</p><pre>circom &lt;file&gt;.circom --wasm --r1cs</pre><p>The proof construction is done via the javascript app <em>snarkjs</em>. First, you download a one-time trusted .ptau setup file from the table <a href="https://github.com/iden3/snarkjs#7-prepare-phase-2">here</a> (the exact file depends on the circuit size — for our app I used power-16) and generate a file with an extension .zkey with</p><pre>snarkjs plonk setup &lt;file&gt;.r1cs &lt;file&gt;.ptau &lt;file&gt;.zkey</pre><p>Now you can produce the proof from typescript or javascript as</p><pre>const snarkjs = require(&quot;snarkjs&quot;)<br>const proof = snarkjs.plonk.fullprove(&lt;input&gt;, &lt;wasm&gt;, &lt;zkey&gt;)</pre><p>where the &lt;parameters&gt; are paths to the files with given extensions.</p><p>We can also use snarkjs to create a smart contract that verifies a given proof. This is how we achieve decentralized verification that we can trust. To generate the contract, use</p><pre>snarkjs zkesv &lt;file&gt;.zkey &lt;contract_name&gt;.sol</pre><p>Now we also have to take care of smart contract parameter construction. This can again be done from typescript as</p><pre>const parameters = await snarkjs.plonk<br>    .exportSolidityCallData(&lt;proof&gt;, &lt;public_values&gt;)<br>    .slice(0, callargs.indexOf(&quot;,&quot;))</pre><h3>Theoretic voting implementation</h3><p>Here we’ll describe how our anonymous voting works. There will be three stages:</p><ul><li>registering an election: define eligible voter addresses,</li><li>registering tickets: voters send their tickets to the smart contract,</li><li>spending tickets: voters spend their tickets by proving their ownership to the smart contract in a zero-knowledge way.</li></ul><p>Specifically, first, we as a voter pick a secret value, our voting option, and define our ticket as <strong>H(secret, option)</strong>, where <strong>H</strong> is some function that hides the input. Those are formally known as one-way hash functions and in our case, we use Poseidon, as it’s snark-friendly.</p><p>Then comes the zero-knowledge proving. We send (from any address) to the contract our voting option, a special serial number, and a zk-snark that says.</p><ul><li>we know a ticket in an array of all tickets,</li><li>for that ticket we know a secret value, such that the ticket is of the form <strong>H(secret, option)</strong> for the given option,</li><li>the given serial number is of the form <strong>H(secret, ticket)</strong>.</li></ul><p>This zk-snark doesn’t reveal the ticket or the secret value. You’re probably wondering what is the purpose of the serial number. As the system doesn’t see the spent ticket it needs a mechanism to prevent it being double spent. So, it requires the serial number to be a unique ticket identifier, but one that doesn’t reveal any information about the ticket itself.</p><p>And that’s it. The contract basically stores the tickets when they are registered and checks that every voter has registered at most one ticket. When it comes to spending tickets, it stores the serial numbers and prevents them from being used again. It, of course, also keeps track of the voting results.</p><p>The complete implementation with a cli app is <a href="https://github.com/kuco23/decentralized-anonymous-voting">here</a>. It’s a bit more complicated as the contract has to store election ids and keep track of the voting period, during which the tickets can be spent. Also, proving a zero-knowledge inclusion of a ticket inside a list of tickets requires a <a href="https://en.wikipedia.org/wiki/Merkle_tree">Merkle tree</a> implementation.</p><h3>ZCash</h3><p>Our implementation was actually a simplified idea of how ZCash implements an anonymous decentralized cryptocurrency. Spending a ticket means destroying a coin that was used to make new coins that are sent to other addresses. Those new coins are encrypted in such a way that recipients can decrypt them, and zero-knowledge proof is used to prove that their encryption doesn’t inflate the destroyed coin’s value.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=95508280cf39" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[SHA-256 in 43 lines of Python]]></title>
            <link>https://nseverkar.medium.com/sha-256-in-43-lines-of-python-329de9095aa4?source=rss-eadd94c100f7------2</link>
            <guid isPermaLink="false">https://medium.com/p/329de9095aa4</guid>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[kuco23]]></dc:creator>
            <pubDate>Tue, 26 Jul 2022 00:37:21 GMT</pubDate>
            <atom:updated>2022-08-10T16:08:24.473Z</atom:updated>
            <content:encoded><![CDATA[<h4>A concise implementation of mathematically designed chaos</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*hGFImVQgADBEkt3IdxET9w.jpeg" /></figure><p>SHA-256 is a one-way hash function. It’s hard to stress the importance of those functions in cryptography and if you want to get some idea, check out <a href="https://medium.com/intuition/one-way-functions-and-ethereum-oracles-f6513e1b2963">this</a> post. Because crypto is cool, I’ll just say that Bitcoin uses SHA-256 in its proof of work, to make blocks hard to mine and thus give time for consensus to take place over the decentralized peer-to-peer network. The proof of work basically requires partially inverting SHA-256, which is hard as SHA-256 is believed to be unpredictable and hides its input behind the chaotic output very well. It’s a mathematical representation of <strong>chaos</strong>.</p><p>It also has a bunch of other useful properties. For example, it provides a computationally unique 256-bit identifier of the input, meaning it’s computationally impossible to find two inputs that give the same output. So, you can hash 1TB of data into just 256-bits that uniquely identify that whole data. BitTorrent uses this to verify large downloaded parts were not tampered with, by matching their hashes with the ones specified in a trusted document (torrent file).</p><p>There’s already a <a href="https://medium.com/@domspaulo/python-implementation-of-sha-256-from-scratch-924f660c5d57">good post</a> on implementing SHA-256 in Python, but I found it slightly over-complicated, so this is an attempt to simplify things by using the <a href="https://pypi.org/project/bitarray/">bitarray</a> library. The point of the post is to make an implementation of SHA-256 that’s short, concise, and easy to understand.</p><p>For the just-give-me-the-code type of people, <a href="https://gist.github.com/kuco23/ca727497e3c285667ccc80fcde41c7cc">here</a>’s the gist (constants K, H, and the standard function _binsum are not included in the line count).</p><h3>Preliminaries</h3><p>If you’ve ever used SHA-256, you’re probably used to inputting any data and getting back some hexadecimal number, e.g.</p><blockquote>e2e7dcf1d4f040269156068f4806cbd5fb054092cc96e5b882a6de0477e2c4b7</blockquote><p>But internally SHA-256 works only with binary/bit arrays. (e.g. <strong>010101</strong>). As they can (and do by our computers) represent all other data, we will just assume input is a binary array and produce another binary array, which can then be converted to hexadecimal.</p><p>To understand SHA-256, we need to explain a few basic operations used to chaotically mess up the input. They are only ever used on bit arrays of length 32 and the length is never affected by them!</p><h4>AND, OR and XOR</h4><p>These operations act on bits (zeros and ones), though we’re going to apply them to bit-arrays bit-by-bit. The following table describes how they operate on bits.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MrlxmLVG2CPgY98N7nrvaA.png" /></figure><p>Some examples:</p><blockquote>1010101010 AND 0101010101 = 0000000000</blockquote><blockquote>1111001111 OR 1111100000 = 1111101111</blockquote><blockquote>1111000001 <strong>XOR </strong>0011000001 = 1100000000</blockquote><p>Note that in Python, <strong>AND </strong>is denoted by <strong>&amp;</strong>, <strong>OR </strong>by <strong>| </strong>and <strong>XOR </strong>by <strong>^ </strong>(though more commonly known as <strong>⊕</strong>).</p><h4>RIGHT SHIFT and ROTR</h4><p>Right-shift is denoted by <strong>&gt;&gt;</strong> and shifts every bit in an array to the right, by the given number. This means, we glue that number of zeros to the left and remove that number of bits from the right (imagine pushing the bits right, having the right-overflow fall off and the left void replaced by zeros):</p><blockquote>1111000001 &gt;&gt; 4 = 0000111100</blockquote><p>Similarly, <strong>ROTR </strong>is just shifting the array cyclicly, meaning we now don’t add zeros to the left, but instead the bits we removed from the right (imagine pushing the bits right and having the right-overflow appear on the left):</p><blockquote>ROTR(111100100101, 4) = 010111110010</blockquote><p>It’s called <strong>ROTR</strong>, as the implementation kind of rotates the bits from the left side to the right.</p><h4>Addition modulo 2³²</h4><p>We want to add binary numbers, represented by bit-arrays. But adding two 32-bit numbers can produce a 33-bit number, whereas we can’t change the bit-array size. This is solved by removing the overflow bits on the left (or more mathematically, calculating the remainder of the division by <strong>2³²</strong>). As for addition itself, this is a basic high-school carry algorithm.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0d33ef49ec5604575dab4342a6401855/href">https://medium.com/media/0d33ef49ec5604575dab4342a6401855/href</a></iframe><p>We’re stopping the algorithm when it would have overflown our 32-bits.</p><h3>SHA-256</h3><p>Sha-256 uses some initial values that pretty much act as a random seed.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f0f4c3fd2938da2b9d1c92b458a665f8/href">https://medium.com/media/f0f4c3fd2938da2b9d1c92b458a665f8/href</a></iframe><p>The values are 32-bit numbers, expressed in hexadecimal; later, we’ll convert them to bit-arrays. The derivation of the above constants won’t matter to us.</p><p>We’ll also use some more specific functions that are just combinations of our previously explained operators:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9e8ed3d79d32e8be21d871f71742e64c/href">https://medium.com/media/9e8ed3d79d32e8be21d871f71742e64c/href</a></iframe><p>SHA-256 takes a binary array and pads it in a very specific way. Remember that the given bit array is of any size, but SHA-256 wants to work with 32-bit arrays. This will be achieved in two steps.</p><p>First, it will pad the given array to be a multiple of 512, so it can then uniformly split it into 512-bit parts. It also wants to encode the information about the given size into the padding, so it pads the <strong>n</strong>-bit array in the following way:</p><ul><li>append the bit <strong>1</strong> to the given array,</li><li>append <strong>k</strong> zeros (<strong>k</strong> is specified later),</li><li>append the 64-bit binary encoding of <strong>n</strong>.</li></ul><p>Now, <strong>k</strong> takes care of us being able to nicely split the given padding into 512-bit blocks. So, <strong>k</strong> is the smallest number making this padding have a length that is a multiple of 512. There are various ways of calculating this. I took a more mathematical approach.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b2a9d3c254b393e6ec6738a9cf61ce45/href">https://medium.com/media/b2a9d3c254b393e6ec6738a9cf61ce45/href</a></iframe><p>Now we’ll just post the whole SHA-256 function and explain the steps after.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/513903072bf23fefee632085c9e0e71e/href">https://medium.com/media/513903072bf23fefee632085c9e0e71e/href</a></iframe><p>First, Kb and Hb are bitarray representations of the previous hexadecimal constants and binsum is applying the previously defined 32-bit summation to sum any (not just two) number of arguments. The chunks function splits an array into an array of fixed-length arrays (in our case 32 and 512). After that:</p><ul><li>[1] We set the compressor variable to our initial “random seed” Hb. Then we iterate over 512-bit chunks of the padded input. Each chunk will later affect the compressor value in some chaotic way.</li><li>[2] The 512-bit chunks are further split into 32-bit pieces, which now act as random seeds on which we apply our previously defined chaotic functions. They are applied 48 (64 <strong>– </strong>16) times to produce a nice mess inside variable W.</li><li>[3] Now we merge the mess with the compressor by applying our chaotic functions (64 times) to its 32-bit parts (the letter variables), while also shuffling them around at each turn.</li><li>[4] Each processed (messed up) 32-bit array is added (binsumed) to the appropriate 32-bit part of the compressor.</li><li>[5] After using all 512-bit chunks of our padded input to mess up with the compressor, it has its 8<strong> </strong>arrays of length 32 glued into one 256-bit array, which is our return value.</li></ul><p>And that’s it for the low-level bit-array SHA-256 implementation!</p><h4>General input and hex output</h4><p>It’s completely up to you how you encode your data into bit-arrays. Here we’ll see one way of doing it and construct a more general SHA-256 that can take strings or integers as input.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/9a230c87e3c5923ff4aa4f0db9eb1df2/href">https://medium.com/media/9a230c87e3c5923ff4aa4f0db9eb1df2/href</a></iframe><p>Let’s demonstrate the chaotic nature of SHA-256 by hashing some large string (e.g. <a href="https://www.bible.com/bible/1/GEN.1.kjv">the first page of the Bible</a>) and comparing it to a hash of that same string, but replacing just one letter (e.g. the second one - I to i):</p><blockquote>1520227ea79705d034bcfe0cc5e22dfdcb7a0959a4185b842c3aa64daa2e2929</blockquote><blockquote>915d2b84debdc0352970d2d40bd6bae5b91d11b5ccd66eb61117ad8840efa4be</blockquote><h4>A note on the differences in implementations</h4><p>We’ve implemented SHA-256 as described in <a href="https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf">this</a> official-looking document, but there are varying versions. E.g. Python’s hashlib accepts the bitarray object, but the outputs are different. The implementation seems to have changed with Python 3.10.0. Anyway, I got into SHA-256 internal workings to match <a href="https://github.com/iden3/circomlib/blob/master/circuits/sha256/sha256.circom">this</a> implementation, done in <a href="https://nuderebatsin-roal.gitbook.io/zkcloud-docs/introduction/circom">circom</a> (a rather obscure language for building arithmetic circuits… that’s another story).</p><h3>Conclusion</h3><p>The point here really was to nicely modularize the SHA-256 function and make it concise in order to easier understand the big picture. I could make it shorter, but it was a sort-of min-max process, where my OCD maximized the code pythonicity and readability.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=329de9095aa4" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[One-way functions and Ethereum oracles]]></title>
            <link>https://medium.com/intuition/one-way-functions-and-ethereum-oracles-f6513e1b2963?source=rss-eadd94c100f7------2</link>
            <guid isPermaLink="false">https://medium.com/p/f6513e1b2963</guid>
            <category><![CDATA[solidity]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[science]]></category>
            <category><![CDATA[cryptocurrency]]></category>
            <category><![CDATA[cryptography]]></category>
            <dc:creator><![CDATA[kuco23]]></dc:creator>
            <pubDate>Tue, 24 May 2022 01:47:28 GMT</pubDate>
            <atom:updated>2022-08-06T23:53:29.660Z</atom:updated>
            <content:encoded><![CDATA[<h4>Mathematics</h4><h4>Understanding a cryptographic notion of commitment</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2wOKl214yWXP1lLhNMTS7A.jpeg" /><figcaption>By <a href="https://www.pexels.com/@jens-johnsson-14223/">Jens Johnsson</a> @ <a href="https://www.pexels.com/photo/brown-wooden-arrow-signed-66100/">pexels</a></figcaption></figure><p>This post is about the various uses of one-way functions, stemming from an idea called commitment. Our main example will be implementing a decentralized voting system (an oracle) on Ethereum (or any other chain that supports smart contracts).</p><h3>One-way functions</h3><p>We say that <strong>f : X → Y</strong> is a one-way function if</p><ul><li>for every <strong>x </strong>in <strong>X</strong> we can quickly calculate <strong>f(x)</strong>,</li><li>for a randomly chosen <strong>y</strong> in <strong>Y</strong> it is almost surely impossible to find any <strong>x </strong>that gives <strong>f(x) = y</strong>.</li></ul><p>This tells us <strong>f</strong> efficiently hides data by being easy to compute, but hard to invert.</p><p>Note that the definition makes no sense if <strong>X </strong>and <strong>Y</strong> are small sets, as then the first point allows us to quickly calculate <strong>f(x) </strong>for every <strong>x</strong> in <strong>X </strong>and compare it with a given <strong>y </strong>in <strong>Y</strong>, contradicting the second point’s condition. So, we really need a large domain <strong>X</strong> and codomain <strong>Y</strong>.</p><p>Another property that is often desirable when considering one-way functions is called no-collision:</p><ul><li>it’s nearly impossible to find any two values <strong>x ≠ y</strong> that give <strong>f(x) = f(y)</strong>.</li></ul><p>The no-collision property is saying that the function should be computationally one-to-one, meaning that in practice, finding two different inputs mapping to the same value is hard. So, it assigns a practically unique value to every input.</p><p>A hash function is a one-way function returning values of some fixed length. This is useful when also assuming no-collision property, as a hash function then hides data and assigns it a unique identifier in the form of some standardized string. This value is often called the data’s fingerprint.</p><p>A big family of hashing functions is called <a href="https://en.wikipedia.org/wiki/Secure_Hash_Algorithms">SHA</a> (Secure Hash Algorithm) and is widely implemented. E.g. when implementing an oracle, we’ll use solidity’s keccak256 and in the Python example, we’ll use sha256. To understand how one of them works, see <a href="https://nseverkar.medium.com/sha-256-in-43-lines-of-python-329de9095aa4">this</a>.</p><h4>A note on the existence of one-way functions</h4><p>It’s somewhat important to know that one-way functions are not yet proven to exist. The examples we have and use seem to work and have thus far stood the test of time. Though as of now, there is still no mathematical proof of them satisfying the one-way condition. Their existence is equivalent to <a href="https://en.wikipedia.org/wiki/P_versus_NP_problem"><strong>P≠NP</strong></a>.</p><h3>Commitment</h3><p>So, how do we use one-way functions? An important application is called commitment. Let’s try to understand what that is with an example.</p><p>A while back my friend and I were talking over messenger and decided to resolve an argument by doing rock-paper-scissors. My friend proposed we each send our answers at the same time. So, I quickly coded up a messenger bot in Python (back then <a href="https://github.com/fbchat-dev/fbchat">this lib</a> used to work), which responded accordingly to rock, paper, or scissors. The time difference in my response was unnoticeable and I won (even when my friend requested best out of three).</p><p>How would we have played this game fairly? By using one-way functions! We want to somehow <strong>commit </strong>to our answers and not be able to change them afterward. The procedure goes like this:</p><ul><li>both sides agree on some no-collision one-way function <strong>f</strong>,</li><li>each side privately picks an answer (rock, paper, or scissors),</li><li>each side commits to their answer by sending the answer mapped by <strong>f </strong>(this is called a commitment) to the other side,</li><li>after each side receives the other side’s commitment, they both reveal their answers and check if the commits were calculated correctly (so, if the commits match the <strong>f</strong> mappings of the revealed answers).</li></ul><p>Does this work? No side can change their answer as that requires finding two different values mapping to the same commitment (which is very hard by the no-collision property). But can the other side get the answer from our commitment? Of course! Our domain only has three elements!</p><p>We solve this by adding a large random number (called salt) to our answer. If that number is e.g. 512-bit, then our domain has <strong>3 * 2</strong>⁵¹² elements and the one-way property assures us that data is well hidden behind our commitment.</p><p>Below, I’ve recreated rock-paper-scissors, where the program commits its answer by printing the commitment and also checks if its proof is correct.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5a7ed70e59ca60dd9ef539249cad4d10/href">https://medium.com/media/5a7ed70e59ca60dd9ef539249cad4d10/href</a></iframe><h3>Decentralized oracles</h3><p>An oracle on a chain that implements smart contracts is a smart contract, providing you with reliable information about the outside world.</p><p>A contract is just a program and needs its code. We make it implement a decentralized voting system. It accepts votes from other users (or contracts), who try to agree on the state of the outside world. From those, it then calculates the most probable answer. The idea is simple. There is only one value known to all participants - the truth. If people want to lie, they will have to align their lies.</p><p>But if all answers sent to the contract are known to all, people can just copy them and thus reproduce the same answer, which might be a lie. One-way functions can solve this. They can hide and commit the votes, so others can’t duplicate them (share the same lie) or change them later.</p><p>The system for voting on a price of a certain coin (e.g. Bitcoin) consists of three stages:</p><ul><li>users submitting hashed prices (votes) to the contract that saves them,</li><li>users revealing the prices to the contract that checks whether they match their previous commitment,</li><li>the contract rewarding users that were the closest to the median value of the submitted prices (i.e. the truth).</li></ul><p>The last point rewards users for contributing and playing according to the rules. This serves as a motivation for participating in the system.</p><p>The below contract, called TSO (Time Series Oracle), gives a more formal idea of what we’re trying to do.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/31f0a135112ca4b06b72e4e9da5dd1b8/href">https://medium.com/media/31f0a135112ca4b06b72e4e9da5dd1b8/href</a></iframe><p>The median and the rewarding system are not implemented. The median can be calculated somewhat efficiently with <a href="https://en.wikipedia.org/wiki/Quickselect">quickselect</a>. The rewarding system has many variations, so there’s a lot of freedom when it comes to implementation.</p><p>As smart contracts only execute when they are called, we can’t calculate the median of the previous epoch and deal rewards until reward is called by someone (anyone) during some later epoch (preferably the next one). This will probably be triggered by the users who know they will be rewarded.</p><p>This was an explanation of a specific oracle, called <a href="https://www.alphaoracle.io/flare-network/ftso/">Flare Time Series Oracle</a> (FTSO), which is implemented on top of the <a href="https://flare.xyz/introducing-songbird/">songbird</a> network.</p><h3>Conclusion</h3><p>It seems that some problems in our world are way harder than other ones. Yet we still don’t have a mathematical proof of this, so we have to assume it’s true. This simple assumption allows us to mathematically construct cryptographic systems that make magic happen. It all seems to depend on whether <strong>P=NP</strong>. If <strong>P=NP</strong> most of the theory behind cryptography is wrong. Let’s keep this in the back of our minds (as far back as possible).</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f6513e1b2963" width="1" height="1" alt=""><hr><p><a href="https://medium.com/intuition/one-way-functions-and-ethereum-oracles-f6513e1b2963">One-way functions and Ethereum oracles</a> was originally published in <a href="https://medium.com/intuition">Intuition</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Number bases and their patterns]]></title>
            <link>https://medium.com/intuition/number-bases-and-their-patterns-34d8ffd498fb?source=rss-eadd94c100f7------2</link>
            <guid isPermaLink="false">https://medium.com/p/34d8ffd498fb</guid>
            <category><![CDATA[numbers]]></category>
            <category><![CDATA[patterns]]></category>
            <category><![CDATA[math]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[mathematics]]></category>
            <dc:creator><![CDATA[kuco23]]></dc:creator>
            <pubDate>Wed, 04 May 2022 07:21:25 GMT</pubDate>
            <atom:updated>2022-08-13T20:48:42.077Z</atom:updated>
            <content:encoded><![CDATA[<h4>Mathematics</h4><h4>Understanding general number bases</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*6nSJIxTd040YhLANLzZusQ.jpeg" /><figcaption>from <a href="https://www.pexels.com/@roman-friptuleac-166600420/">Roman Friptuleac</a> at <a href="https://www.pexels.com/">pexels</a>.</figcaption></figure><p>We’ve grown accustomed to visualizing numbers in the decimal system, even though the evolution of that representation was not entirely trivial. The patterns of counting are burned into our subconscious and not many people consciously understand how it all works.</p><p>This post is about understanding humanity’s way of encoding large concepts into small data. It’s going to try to separate the notion of a number from its representing string. It does require some basic knowledge of combinatorics.</p><p>Our <strong>10 </strong>fingers made us love the decimal system and somewhat randomly use the following symbols</p><blockquote>0, 1, 2, 3, …, 9.</blockquote><p>To avoid confusion, anything expressed with those symbols will be viewed as an actual abstract number, unless explicitly stated otherwise. Also, note that letters denoted <strong>n</strong>, <strong>k</strong>, <strong>i</strong>, <strong>l</strong>, and <strong>b</strong> are variables, representing general integer values.</p><h3>Understanding number bases</h3><p>A mathematical view of a number is abstract, meaning it doesn’t have a visual representation. But our interpretation of reality is mostly visual, so we have found it useful to define systems that allow us to “see ”numbers.</p><p>Early examples, such as roman numerals, were very primitive because they used too much space. Strings of length <strong>l </strong>could only represent about <strong>1000l </strong>numbers. Conversely, to represent a number <strong>n</strong> they used strings of about length <strong>n/1000</strong>:</p><blockquote>90231 = MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMCCXXX.</blockquote><p>After a while, we learned to optimize things by using some combinatorics. E.g. if we have <strong>3 </strong>different symbols to work with, say</p><blockquote>x, y, z,</blockquote><p>we can represent <strong>3^l</strong> different length-<strong>l</strong> strings from those symbols. E.g. taking <strong>l=3 </strong>gets us <strong>27</strong> distinct combinations:</p><blockquote>xxx, xxy, xxz, xyx, xyy, xyz, xzx, xzy, xzz,</blockquote><blockquote>yxx, yxy, yxz, yyx, yyy, yyz, yzx, yzy, yzz,</blockquote><blockquote>zxx, zxy, zxz, zyx, zyy, zyz, zzx, zzy, zzz.</blockquote><p>Let’s generalize things a bit and say we have a set <strong>A</strong> containing <strong>b</strong> symbols. How do we associate numbers with strings formed from symbols in <strong>A</strong>? In other words, how do we order strings over <strong>A</strong>?</p><p>We want to be space-friendly and require lower numbers to be able to use less space (we don’t want giant strings representing small numbers). So, we start by (arbitrarily) ordering the set of <strong>b</strong> symbols <strong>A</strong> (strings of length one):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/289/1*cDVJeVZ_Z3D2MAfnvI-szw.png" /></figure><p>We just counted through the first <strong>b</strong> numbers (<strong>0</strong>,<strong>1</strong>,<strong>2</strong>,…,<strong>b-1</strong>) by going through all length-one strings. Let’s move on to length-two. There is one natural way of ordering them:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/528/1*cNdhHdRq6meoA5ufSLMA5g.png" /></figure><p>Try to understand the pattern of our counting/ordering and generalize it to strings of any length. Note that <strong>a0</strong> represents zero, so in the first line <strong>a0</strong>s disappear and we again get the length-one strings. In our standard base, this looks like</p><blockquote>006051 = 6051, 00001 = 1, 00000 = 0 = “”, …</blockquote><p>So, our base systems are designed in a way that strings of a certain length can also represent the values of all lower-length strings, by left-padding them with zeros. As strings of length <strong>n</strong> can encode <strong>b^n</strong> different combinations, they can represent ALL numbers from <strong>0</strong> to <strong>b^n - 1</strong>.</p><p>How do we explicitly calculate the number a given string represents? Let’s say we have some length-<strong>l </strong>string</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/250/1*VWeIknOZwovo-S1a8HKDiw.png" /></figure><p>Let the <strong>i</strong>-th symbol of <strong>s </strong>be indexed by <strong>ki</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/146/1*wULhG2pOYjD4kOXQ1OYnSQ.png" /></figure><p>Let’s think about the number of strings we had to count through to arrive at <strong>s</strong>. Recalling our string-ordering pattern, it’s easy to see that all strings smaller than <strong>s </strong>not starting with symbol <strong>s1 = ak1</strong> are exactly</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/237/1*mP5v3CkwQLRqKe8BRDETfw.png" /></figure><p>In every line we go through all possible combinations of <strong>x</strong> symbols and as in every line there are <strong>l-1 </strong>of<strong> x</strong>’s to permute with a total of <strong>k1</strong> lines, we get</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/149/1*JoOnQLPmiLjIMr05-Egq4g.png" /></figure><p>different strings. After going through all those, we finally arrive at strings that start with the symbol</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/146/1*rpF1Leai0qEBzwMbwzM6uw.png" /></figure><p>Now all that’s left is getting to <strong>s</strong> from</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/191/1*KY6mWwxTtoMd4LDpDpcsAg.png" /></figure><p>As <strong>s1</strong> is fixed, this is exactly like counting from <strong>a0 </strong>(=<strong>0</strong>) to</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/158/1*jGzZV6g4tSYUoRpvt4IdMQ.png" /></figure><p>If we denote the number evaluation of a given string by<strong> […]</strong>, then we’ve just derived</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/517/1*iJsuyOQDZdMUpDJprVIx_A.png" /></figure><p>as counting to <strong>s</strong> required counting to <strong>s2…sl</strong> and also going through the previously mentioned strings. Continuing inductively gets us</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/702/1*t_TOOJ_HTNK2-Q-m2FQOWw.png" /></figure><p>We’ve obtained a function telling us the numeric value of its base-<strong>b</strong> representation. Also notice that for all <strong>i</strong> it holds <strong>0 ≤ ki &lt; b</strong>.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/5c3e1126ae7d3055f2ba3f2022a046bc/href">https://medium.com/media/5c3e1126ae7d3055f2ba3f2022a046bc/href</a></iframe><p>How do we do the converse? If we have some number <strong>n</strong>, we’d like to represent it. By our previous result, we can express</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/554/1*JFl7EYLnUYAo3YmCE8TkHQ.png" /></figure><p>but we don’t know any <strong>k</strong>’s (indices of base-<strong>b</strong> symbols). Let’s define</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/599/1*FA7qVkJd3oYK9RVsKwdNjQ.png" /></figure><p>and notice that</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/783/1*JzMOEob0ADNWLoCIL7aaaA.png" /></figure><p>Remember we have <strong>0 ≤ kl &lt; b</strong>. The above then says <strong>kl</strong> is the remainder of <strong>n</strong> when dividing by <strong>b</strong>. It also says <strong>m</strong> is the result of doing integer division by <strong>b</strong> on <strong>n</strong>.</p><p>We’ve obtained <strong>kl</strong> and <strong>m</strong>. To get the rest of the<strong> k</strong>’s, we continue the process inductively on <strong>m</strong>. Basically, the remainder and division operators together <a href="https://www.geeksforgeeks.org/p5-js-pop-operation-in-stack/">pop</a> the index of the base string’s right-most symbol.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c412fc4739ec3b7ed75e06031472cb6b/href">https://medium.com/media/c412fc4739ec3b7ed75e06031472cb6b/href</a></iframe><p>One fairly useful application of the code is encoding strings as numbers:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/47a9331565f434cf349ef9ee4875f681/href">https://medium.com/media/47a9331565f434cf349ef9ee4875f681/href</a></iframe><p>We are basically counting through all possible strings. Taking only the first <strong>16</strong> symbols gets us the formal representation of the hexadecimal system.</p><p>Another useful application is representing a sequence of integers as one integer (this can be seen as an extension of the <a href="https://en.wikipedia.org/wiki/Pairing_function">Cantor pairing function</a>):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d116c2b4d3fa0503ed5a1fdf50182f43/href">https://medium.com/media/d116c2b4d3fa0503ed5a1fdf50182f43/href</a></iframe><p>It’s really fun to play around with the code and see what counting looks like in different bases and with different sets of symbols. Though there’s one special case where our code and theory don’t work. It’s when <strong>b=1</strong>. This is called the unary system and can (easily) be implemented separately. Using symbol <strong>I</strong>, counting in it looks like</p><blockquote>I, II, III, IIII, IIIII, IIIIII, IIIIIII, IIIIIIII, …</blockquote><p>The main difference is that we don’t treat <strong>I</strong> as zero and thus the length of our strings carries a lot (all) of the information. In this way, the unary system is special and treated separately.</p><p>A fun fact is that formalizing natural numbers in mathematics is done via the unary system. Check out <a href="https://medium.com/p/8b5549f1cf9c">this</a> post for more info.</p><h3>Picturing patterns</h3><p>It’s kind of interesting that base pattern translations reduce to two simple functions. I wanted to see what this pattern encoding looks like. Though there is no one canonical way of making an image out of this, so I just played around with it a bit.</p><p>For a base-<strong>b</strong> system, we need to have <strong>b</strong> distinct symbols. One way of getting them is representing the <strong>i</strong>-th symbol by the decimal representation of <strong>i </strong>(this is just using str for our sym). One pattern-producing question is about the ratio between this kind of representation of <strong>i</strong> in the base-<strong>j</strong> system and that of <strong>j</strong> in the base-<strong>i</strong> system. Concretely for some fixed <strong>i ≥ 2</strong> and <strong>j ≥ 2</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b1fbc7b1eb4c8a8e0df4ed4e7b850d82/href">https://medium.com/media/b1fbc7b1eb4c8a8e0df4ed4e7b850d82/href</a></iframe><p>Translating this to an image by making the ratio determine image color, looks like:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/df2934559c40160374b27724da991f84/href">https://medium.com/media/df2934559c40160374b27724da991f84/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*WEg_tFT2I2EVq1__HW4ZGA.png" /><figcaption>Applying rgbfun to every pixel/coordinate of a 4000x4000 image.</figcaption></figure><p>Another similar example is:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e3ebcd75aabf923ec179873d81a87327/href">https://medium.com/media/e3ebcd75aabf923ec179873d81a87327/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qv5ljmMS6I-DPaAinGSmnA.png" /><figcaption>Applying rgbfun to every pixel/coordinate of a 2000x2000 image.</figcaption></figure><p>Some other fun projects could be using an alphabet <strong>{x,(,)}</strong> and finding out which numbers encode to a correct bracket placement. For example <strong>(x(xx((x))x))</strong> is ok, while <strong>(x(x))))</strong> isn’t. Or using an alphabet <strong>{x,y,+,×,=}</strong> you can find out which numbers encode to a syntactically correct equation that has a real-valued solution. Maybe this sounds dumb, but there are <a href="https://math.ucr.edu/home/baez/roots/">incredibly cool things</a> that can happen when considering random connections.</p><h3>Conclusion</h3><p>We are pattern-recognizing machines. We sense patterns and use them to solve problems, encode data, communicate, and do a whole bunch of other stuff. Number bases and pattern-filled images are great examples of our pattern-matching abilities.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=34d8ffd498fb" width="1" height="1" alt=""><hr><p><a href="https://medium.com/intuition/number-bases-and-their-patterns-34d8ffd498fb">Number bases and their patterns</a> was originally published in <a href="https://medium.com/intuition">Intuition</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Basics of Mathematical Cryptography]]></title>
            <link>https://medium.com/intuition/basics-of-mathematical-cryptography-408fdee23826?source=rss-eadd94c100f7------2</link>
            <guid isPermaLink="false">https://medium.com/p/408fdee23826</guid>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[math]]></category>
            <category><![CDATA[science]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[kuco23]]></dc:creator>
            <pubDate>Sat, 16 Apr 2022 00:02:29 GMT</pubDate>
            <atom:updated>2022-07-15T15:50:35.105Z</atom:updated>
            <content:encoded><![CDATA[<h4>Mathematics</h4><h4>Symmetric and asymmetric encryption with examples in Python</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*uBg-CR-sjulWolMO2fDozQ.jpeg" /><figcaption>source: <a href="https://www.pexels.com/@cottonbro/">cottonbro</a> at <a href="https://www.pexels.com/">pexels</a></figcaption></figure><p>Cryptography has been around for ages, but now, due to all the information technology, it has become an integral part of our daily lives (without us really noticing). It also allows for crazy decentralized things like Bitcoin and Ethereum to work.</p><p>This post will explain some basic notions of cryptography and show how they allow any two strangers to securely communicate through insecure (public) channels. We’ll also implement everything in Python.</p><p>If you know what a prime number is, then you know enough math for this post. If you’ve heard of modular arithmetic, you know too much :)</p><h3>Symmetric encryption</h3><p>This is a class of cryptographic protocols. It requires two functions</p><blockquote>e(k, m) and d(k, x),</blockquote><p>where<strong> e</strong> encrypts message <strong>m</strong> using key <strong>k</strong>, and <strong>d</strong> decrypts <strong>x</strong> by using key <strong>k</strong>. We expect that <strong>d </strong>decrypts an encrypted message when the same key<strong> </strong>is used. So, for every key <strong>k </strong>and message <strong>m</strong>, we have</p><blockquote>d(k, e(k, m)) = m.</blockquote><h4>Caesar cipher</h4><p>An early example of a cryptographic protocol was created by Julius Caesar and is therefore called the Caesar cipher. It’s pretty simple as it encrypts messages just by cyclicly shifting their letters.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c09fa5927c50cd964e2e0e1f61fd2243/href">https://medium.com/media/c09fa5927c50cd964e2e0e1f61fd2243/href</a></iframe><p>We have our encryption algorithm <strong>e</strong>, but how do we decode an encrypted message? We just shift every letter back for as many places as it was shifted forward. If we take the shifting number <strong>k</strong> to be the secret key, then we’ve described a simple symmetric encryption system.</p><p>This is not a good encryption algorithm though. If anyone was to learn how we encrypt our data, they could pretty soon find the shifting number and decode any given text. How do we solve this?</p><p>We should have a cryptographic algorithm that is hard to crack, even if an attacker knows its implementation. So, it is absolutely necessary that the brute force approach of testing every possible key doesn’t work. In other words: the set from which our keys are chosen should be big.</p><h4>Permutation cipher</h4><p>Our shifting is a specific permutation of letters. What if we then generalize things by choosing a permutation of our alphabet and take it as our private key?</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d0a3f5b9c8e74e355a0d237f9a1ad650/href">https://medium.com/media/d0a3f5b9c8e74e355a0d237f9a1ad650/href</a></iframe><p>If an attacker knows our protocol, they would still need to try every permutation to crack the code. Using an alphabet with <strong>n </strong>letters, there are <strong>n!</strong> permutations, i.e. <strong>n!</strong> keys. Picking <strong>n ≥ 20 </strong>should take care of him being unable to find the one we chose, as</p><blockquote>20! = 2432902008176640000.</blockquote><p>Or can he?</p><p>Maybe the attacker knows more than just the brute-force approach of checking every permutation. He could for example realize that in English, some letters are used more commonly than others. Maybe he also knows some often-occurring patterns. Such methods are called statistical analyses and can easily break some safe-looking systems.</p><h4>The problem with symmetric encryption</h4><p>There exist far better (and way more sophisticated) symmetric cryptosystems that solve our previous problems. But by our definition of symmetric encryption, they all require both sides to possess the same private key. How do we communicate this key if all we can use are public channels? The answer is asymmetric cryptography.</p><p>Asymmetric cryptosystems enable two strangers to construct the same shared key, which is safely hidden from anyone else. This key can then be used as a private key of some symmetric cryptosystem.</p><h3>Diffie-Hellman key exchange</h3><p>The main difference here is that we now have two keys. One is public and the other one is private. Anyone can encrypt a message using the public key, while decryption requires the private key.</p><p>The simplest asymmetric encryption system is based on the Diffie-Hellman key exchange. Like many other cryptosystems, it heavily relies on the theory of cyclic groups, which is not that difficult to understand.</p><h4>Modular arithmetic</h4><p>Modular arithmetic is pretty much the same as normal arithmetic, except we equate a few different elements, which makes things look more circular.</p><p>Formally, for a given positive integer <strong>n</strong>, we have</p><blockquote>a = b (mod n) if n divides (b - a)</blockquote><p>Some examples:</p><blockquote>12 = 0 (mod 4), 13 = 1 (mod 4), 14 = 2 (mod 4),</blockquote><blockquote>12 = 2 (mod 5), 13 = 3 (mod 5), 14 = 4 (mod 5),</blockquote><blockquote>1021 = 1 (mod 10).</blockquote><p>Basically, the <strong>mod n</strong> elements are all possible remainders of the division by <strong>n</strong>:</p><blockquote>0, 1, 2, 3, …, n - 2, n - 1.</blockquote><p>Each of those represents all elements equal to it in <strong>mod n</strong>. In most programming languages, we can get this remainder by</p><blockquote>x % n</blockquote><p>It’s not hard to see that for a prime number <strong>p</strong>, every element other than <strong>0</strong> has an inverse in <strong>mod p</strong>. That means for every <strong>x ≠ 0</strong> there is a <strong>y</strong> such that</p><blockquote>x ⋅ y = 1 (mod p).</blockquote><p>In ordinary arithmetic, we denote <strong>y</strong> as <strong>1 / x</strong>, so we’ll also do it like this here. We’ll also rely on a pretty obvious fact that in the modular arithmetic we have</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/307/1*jX42JpuzYilFWvcm32nzKA.png" /></figure><p>for any numbers <strong>a</strong>, <strong>b </strong>and <strong>q</strong>.</p><h4>Hard problem assumptions</h4><p>For our algorithm to work, we need to assume that some problems are hard. This means currently, we don’t know of an algorithm that could solve them without wasting a hundred years and many computers.</p><p>Those problems are expressed in a form of one-way functions. A function <strong>f</strong> is one-way if it satisfies:</p><ul><li>For every <strong>x</strong> the value <strong>f(x)</strong> is easily computable,</li><li>For any value <strong>y </strong>any <strong>x</strong> that gives <strong>f(x) = y</strong> is very hard to compute.</li></ul><p>A specific function that seems to satisfy the two conditions is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/374/1*lhhRPntoWiJdNGVhmtCsGw.png" /></figure><p>where <strong>p </strong>and <strong>q </strong>are some carefully chosen prime numbers. We assume such a pair <strong>(p, q)</strong> in what follows, with every arithmetic operation being done in <strong>mod p</strong>.</p><p>The task of determining <strong>x</strong> from <strong>q^x</strong> is called the <strong>Discrete logarithm problem </strong>and is closely related to the <strong>Diffie-Hellman problem</strong>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/655/1*E1NxCuNX0mzluryF892e7A.png" /></figure><p>The only known solution to the above is through solving the Discrete logarithm problem. We assume solving the Diffie-Hellman problem is hard.</p><h4>ElGamal Public Key Cryptosystem</h4><p>The beauty of our protocol is that two people Alice and Bob, each with their own secret numbers <strong>a </strong>and <strong>b</strong>,<strong> </strong>can privately communicate over insecure channels. All this without any prior private interaction.</p><p>All they have to do is publicly reveal <strong>A = q^a </strong>and <strong>B = q^b</strong>.<strong> </strong>Then each of them can easily construct <strong>q^(ab) = A^b = B^b</strong>, while anyone else has a hard time doing so (by the Diffie-Hellman assumption). This value is called the shared key.</p><p>Let’s say Alice wants to send a message<strong> m</strong> to Bob:</p><ul><li>Alice encodes <strong>m </strong>as an integer <strong>n</strong>, takes <strong>B</strong>,<strong> </strong>and calculates <strong>B^a = q^(ba)</strong>. She then sends <strong>n </strong>⋅ <strong>B^a</strong> to Bob.</li><li>Bob receives <strong>X</strong>, calculates <strong>X / A^b</strong>, and gets <strong>n</strong>. He then decodes<strong> n </strong>into <strong>m</strong>.</li></ul><p>Note that every string is basically encoded as an integer by your computer. Concretely, <a href="https://stackoverflow.com/questions/55407713/how-to-encode-a-text-string-into-a-number-in-python">here</a> are a couple of ways to do it.</p><p>Why exactly can’t some attacker get <strong>n</strong>? Let’s think about what he sees. He only ever sees <strong>A</strong>, <strong>B, </strong>and <strong>X </strong>as everything else was held locally (outside the insecure communication channel). If he can get <strong>n</strong>, he can get <strong>q^(ab) = X / n</strong>, which is the shared key. So, does getting <strong>n</strong> breaks the Diffie-Hellman assumption?</p><p>It would if the attacker only saw <strong>A</strong> and <strong>B</strong>, but he also sees <strong>X</strong>. Why is this a problem? The attacker might not know how to find <strong>q^(ab)</strong>, but he might be able to test whether a given number is equal to it. In turn, he is also able to test if <strong>X</strong> is an encryption of a given message. E.g. if our message is either <strong>yes </strong>or <strong>no</strong>, he can test each one.</p><p>But we can solve this. All we have to do is make <strong>n</strong> (and therefore <strong>X</strong>) look random to the attacker. We do this by choosing a random element <strong>r</strong> and then sending <strong>(n, r)</strong> instead of <strong>n</strong>. This pair is encoded as a natural number (e.g. via the <a href="https://en.wikipedia.org/wiki/Pairing_function">Cantor pairing function</a>), which inherits at least some randomness of <strong>r</strong>. This randomization process is called salting (or padding). Our salting is very primitive and for a more advanced example, you should check <a href="https://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding">OAEP</a>.</p><p>Another thing we have to mention is that sending two messages using the same public key reveals their ratio (it’s equal to encryptions’ ratio). So, each time we send something, a new sending key has to be generated and treated as we’ve treated the private key. Its public pair can be sent along with the message.</p><h4>Implementation</h4><p>Python having an advanced pow function greatly simplifies the implementation of our algorithm, as it can quickly <a href="https://en.wikipedia.org/wiki/Exponentiation_by_squaring">power</a> and <a href="https://math.stackexchange.com/questions/3098589/using-fermats-little-theorem-to-find-multiplicative-inverse">find inverses</a> in modular arithmetic.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c99a1dd9b91a87cee6ba2a40abd53aff/href">https://medium.com/media/c99a1dd9b91a87cee6ba2a40abd53aff/href</a></iframe><p>Above, we’ve named our private key a_pvk and our public key a_pbk. As the other side’s public key b_pbk is public, it can also be used in our function.</p><p>The tough part is generating a safe prime pair <strong>(p, q)</strong>. We can get it on the internet, or use the <a href="https://pypi.org/project/cryptography/">cryptography</a> python library. Whatever the case, we only need to get it once. From then on generating keys is easy.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/354d7a815d3704debc63d6ef646936b7/href">https://medium.com/media/354d7a815d3704debc63d6ef646936b7/href</a></iframe><p>Now we’ll add the salt and text encodings to define our whole cryptographic system</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c5c716ba1c663c8aca55ad19d605885e/href">https://medium.com/media/c5c716ba1c663c8aca55ad19d605885e/href</a></iframe><p>Note that we can only send numbers between <strong>0</strong> and <strong>p - 1</strong> as those are all the representatives (remainders) in <strong>mod p</strong>. So, we have to watch out that <strong>nr</strong> doesn’t go over <strong>p - 1</strong>, which means that the message <strong>m</strong> should be appropriately small. To send larger messages, we have to send them in parts and then concatenate.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/69e8739ededb0ab55ec2b1d18ee1744c/href">https://medium.com/media/69e8739ededb0ab55ec2b1d18ee1744c/href</a></iframe><p>With this, you can easily implement a trustless cryptographically secure messenger service (e.g. through <a href="https://www.pubnub.com/">PubNub</a>). Though you should still use libraries like cryptography as there are always subtleties you can’t afford to miss when implementing such things.</p><h3>Conclusion</h3><p>We’ve seen some simple symmetric cryptosystems, so we got used to the whole cryptography thing. Then we learned how to implement a fairly simple but powerful algorithm, allowing private communication through public channels.</p><p>Another similar (but more widely used) cryptosystem is the <a href="https://en.wikipedia.org/wiki/RSA_(cryptosystem)">RSA</a>. It’s a bit more complicated and relies on the fact that finding a decomposition of a given number is a difficult problem. It too is entirely based on results from modular arithmetic (or lack thereof).</p><p>All asymmetric cryptosystems rely on the existence of one-way functions. This is closely related to the <strong>P=NP</strong> question, which remains open. The sad fact is that if <strong>P=NP</strong>, we lose a lot of our theory and cybersecurity. Let’s hope that <strong>P≠NP</strong> or that it won’t be solved any time soon.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=408fdee23826" width="1" height="1" alt=""><hr><p><a href="https://medium.com/intuition/basics-of-mathematical-cryptography-408fdee23826">Basics of Mathematical Cryptography</a> was originally published in <a href="https://medium.com/intuition">Intuition</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How math generalizes everything]]></title>
            <link>https://nseverkar.medium.com/how-math-generalizes-everything-554aa6d7a821?source=rss-eadd94c100f7------2</link>
            <guid isPermaLink="false">https://medium.com/p/554aa6d7a821</guid>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[education]]></category>
            <category><![CDATA[math]]></category>
            <category><![CDATA[science]]></category>
            <dc:creator><![CDATA[kuco23]]></dc:creator>
            <pubDate>Sat, 02 Apr 2022 20:03:44 GMT</pubDate>
            <atom:updated>2022-08-06T23:50:43.895Z</atom:updated>
            <content:encoded><![CDATA[<h4>Some examples of generalizations in mathematics</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-7gdz3wsdabGBCEJRSolzg.jpeg" /></figure><p>Generalizations are the key to understanding high-level mathematics. The more advanced math is, the more abstract generalizations you’ll encounter.</p><p>The reason is we often face complex objects and try to deconstruct them to see what their most descriptive properties are. In that way, we can only focus on individual properties and also recognize them in other objects. Studying one property can thus be applied to a wide class of objects.</p><h3>Equality</h3><p>Mathematicians fear redefining things. They like their objects to be immutable. And this is very noticeable when generalizing equality. We never redefine it. We view it as a relation on a set whose elements we wish to equate differently.</p><p>What’s a relation? It can be viewed as a function <strong>R(x,y) </strong>(usually denoted as<strong> xRy</strong>) telling you whether a given pair <strong>(x,y)</strong> has a certain property (i.e. whether <strong>x </strong>and <strong>y</strong> are related). There’s a bit of a language barrier here, as saying <strong>x</strong> and <strong>y</strong> are in a relation does not necessarily mean that <strong>y</strong> and <strong>x</strong> are in a relation… we’ll figure it out.</p><p>Let’s say we have a relation <strong>≡ </strong>that looks like equality. Then it should satisfy the following properties:</p><ul><li>for every <strong>x</strong> we must have <strong>x ≡ x</strong>,</li><li>if we have<strong> x ≡ y</strong>, then we must have <strong>y ≡ x</strong>,</li><li>for every <strong>x</strong>, <strong>y</strong> and <strong>z</strong> we must have <strong>x ≡ y</strong> and <strong>y ≡ z</strong> implying <strong>x ≡ z</strong>.</li></ul><p>Those conditions are called reflexivity, symmetry and transitivity. A relation <strong>≡</strong> satisfying the above is called an equivalence relation.</p><p>Let’s look at an example of set size equality. Two sets have equal size when there is a bijection between them. We can check if this satisfies our conditions:</p><ul><li>The identity function is a bijection from any set to itself, so every set has a size equal to its own.</li><li>If we have a bijection from <strong>X</strong> to <strong>Y</strong>, then its inverse is a bijection from<strong> Y</strong> to <strong>X</strong>.</li><li>If we have a bijection <strong>b</strong> from <strong>X</strong> to <strong>Y</strong> and a bijection <strong>c</strong> from <strong>Y</strong> to <strong>Z</strong>, then the composition <strong>c ∘ b</strong> is a bijection from<strong> X</strong> to <strong>Z</strong>.</li></ul><p>In this context, we can equate two sets that have the same size. <a href="https://medium.com/@nseverkar/for-every-infinity-there-exists-a-bigger-infinity-47c7a3a8f420">Here</a> I expand on the concept.</p><p>We can represent an equivalence relation on a set <strong>X </strong>by gathering the equivalent elements in the same set. We then view those sets as points and call them equivalence classes. They form a partition of <strong>X</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*YvDjkhL3yfnNVfgJ0F-M3w.png" /><figcaption>Some equivalence relation on<strong> X = {1, 2, 3, …, 15}</strong>.</figcaption></figure><h3>Ordering</h3><p>Here we generalize less-or-equal as a relation on a certain set, by extracting the relevant properties:</p><ul><li>for every <strong>x </strong>we must have<strong> x ≤ x</strong>,</li><li>for every <strong>x</strong>,<strong> y</strong> and <strong>z </strong>we must have <strong>x ≤ y</strong> and <strong>y ≤ z</strong> implying <strong>x ≤ z</strong>,</li><li>if <strong>x ≤ y</strong> and<strong> y ≤ x</strong> then <strong>x = y</strong>.</li></ul><p>Any <strong>≤</strong> satisfying the above is called a partial order and is intuitively treated as a version of less-or-equal. An example of such an order is divisibility over natural numbers. So <strong>m ≤ n</strong> when <strong>m | n</strong>, meaning <strong>m</strong> divides <strong>n</strong>:</p><ul><li>obviously for every <strong>x</strong> we have <strong>x | x</strong>,</li><li>if <strong>x | y</strong> and <strong>y | z</strong>, then there are <strong>q</strong>, <strong>h</strong> such that <strong>y = q ⋅ x</strong> and <strong>z = h ⋅ y</strong>, so <strong>z = h ⋅ q ⋅ x</strong>, implying <strong>x | z</strong>,</li><li>if <strong>x | y</strong> and <strong>y | x</strong>, you can check that the only possibility is <strong>x = y</strong>.</li></ul><p>We often visualize partial orders with a <a href="https://www.geeksforgeeks.org/discrete-mathematics-hasse-diagrams/">Hasse diagram</a>. The connected elements are related and the one higher is on the right side of the relation (larger). The diagram uniquely represents our partial order.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/340/1*lGCGdY0R3PBnzXEep9JSEg.png" /><figcaption>Hasse diagram for divisibility.</figcaption></figure><p>There is one important property missing though. It’s called totality and requires every two elements to be comparable. Meaning either <strong>x ≤ y</strong> or<strong> y ≤ x</strong>. In that case, the Hasse diagram is always a straight line.</p><p>This theory is widely applied. One instance is the theory of <a href="https://en.wikipedia.org/wiki/Incidence_algebra">Incidence algebras</a> in combinatorics, with its main result being <a href="https://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula">Möbius inversions</a>.</p><h3>Algebraic operations</h3><p>We know how to add and subtract or multiply and divide numbers. How can we transfer this to some other abstract sets?</p><p>We recognize that those are binary (take two arguments) functions that satisfy some conditions. An important generalization is that of a group, which is a set <strong>G</strong> with some binary operation<strong> f(x, y)</strong>, denoted by<strong> x ⋅ y</strong>, obeying the following conditions:</p><ul><li><strong>(x ⋅ y) ⋅ z</strong> = <strong>x ⋅ (y ⋅ z)</strong>,</li><li>there exists an element <strong>e</strong>, such that <strong>x ⋅ e = e ⋅ x = x </strong>for all<strong> x</strong> in <strong>G</strong>,</li><li>for every <strong>x</strong> in <strong>G</strong>, there exists <strong>y</strong> in <strong>G</strong>, such that <strong>x ⋅ y = y ⋅ x = e</strong>.</li></ul><p>The first point is called associativity and implies that we can forget about the bracket placements in any given expression (this implication is not entirely trivial). We call the special element <strong>e</strong> a unit and can easily prove it’s unique: If there are two units <strong>e</strong> and <strong>u</strong>, then by using their definitions, we get</p><blockquote>e = e ⋅ u = u</blockquote><p>The third point gives groups their symmetry by including inverses. An element is a reflection of its inverse.</p><p>There are various examples of groups, like</p><ul><li>integers with addition (unit is <strong>0</strong>),</li><li>non-zero rational numbers with multiplication (unit is <strong>1</strong>),</li><li>bijections (on a fixed set) with composition (unit is the identity function).</li></ul><p>A very important example is that of <a href="https://en.wikipedia.org/wiki/Cyclic_group">cyclic groups</a>. A lot of cryptography relies on theorems from group theory, applied to cyclic (and elliptic curve) groups.</p><p>If we omit the inverse condition of a group, we get monoids. An example is to consider finite strings over some alphabet, e.g. <strong>{x,y,z}</strong>. The elements look like</p><blockquote>xyz, xyy, zzyzyy, z, “” (empty string), …</blockquote><p>We define multiplication as concatenation and see that it’s associative. The unit is the empty string. This is called the free monoid over <strong>{x,y,z}</strong>.</p><h3>Distances</h3><p>Let’s consider distances in our residing 3d space. From Pythagoras’ theorem, we can calculate the length of a certain 3d-vector as:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/499/1*jDDSLnRy4T0k7L1fr2EaZw.png" /></figure><p>The distance between two points is the length of the vector from one point to another, so</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/293/1*mG5uveIbzJVH196Bel15pw.png" /></figure><p>We can extend the definition of a distance to be more general. We say that the properties defining a distance are:</p><ul><li><strong>d(x, y) = 0</strong> if and only if<strong> x = y</strong>,</li><li><strong>d(x, y) = d(y, x)</strong>,</li><li><strong>d(x, z) ≤ d(x, y) + d(y, z)</strong>.</li></ul><p>The first one says the only case where the distance between two points is <strong>0 </strong>is when the points are the same. The second one says the distance from <strong>x</strong> to <strong>y</strong> is equal to the distance from <strong>y</strong> to <strong>x</strong>. The third one is called triangle inequality and requires that traveling from <strong>x </strong>directly to <strong>z</strong> is always faster than going through some other point<strong> y</strong>.</p><p>Now, we can talk about what balls look like in this generalized distance. A ball around an element <strong>a</strong> with radius <strong>r &gt; 0</strong> is defined as the set of all points <strong>x</strong> with <strong>d(a, x) &lt; r</strong>. Visualizing balls in some given distance can be challenging but gives you an insanely useful intuition about the space.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/643/1*1rc004d1XAY_r72tYGc_Zg.png" /><figcaption>A unit ball around <strong>(0,0)</strong> in the metric <strong>d((x1, y1), (x2, y2)) = max(|x1 - x2|, |y1 - y2|)</strong>.</figcaption></figure><p>Again, we get an example when considering strings over some alphabet, say <strong>{x,y,z}</strong>. Except now the strings are infinite, e.g.</p><blockquote>xyzzzyzzzzyzzxyzxxxzyyzyzzzzzzzzz…,</blockquote><blockquote>yyyzzzxxxyyyzzzxxxyyyzzzxxxyyyzzz…</blockquote><p>We want to define a distance between two different strings <strong>s </strong>and <strong>r</strong>. The following metric formalizes the idea that the closeness of two strings is determined by the number of symbols they have in common at the beginning:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/354/1*FNQJOS9qO1NqPGu2cdSB8g.png" /></figure><p>Try to visualize which strings are close and which are far. Or what balls around some string <strong>a</strong> look like. They should sort of look like trees. The lower the radius, the higher the trunk.</p><p>Another example is viewing functions as vectors. That is basically the whole point of the theory called functional analysis. For two functions <strong>f</strong> and <strong>g</strong>, both mapping from some set <strong>X</strong> to the set of real numbers, we can define the distance between them as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/410/1*wZp5vfnhTt327fGZLP1oKA.png" /></figure><p>This says the distance between two functions is the maximum (supremum) distance between their values. Now a whole range of questions opens up. What does the convergence of a function sequence look like in this metric? Is the limit unique?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/512/1*edJl2AWju08RnQG6kVWA9A.jpeg" /><figcaption>A unit ball around a function from reals to reals (its graph is in black). Any function with a graph inside the above belt is in the ball (three examples are drawn in gray).</figcaption></figure><p>Don’t think this generalization stops here. We have a notion called a topology, which further generalizes distances (in a way). It only tells us what the balls of a given space are. And it turns out that this is enough to define limits, which means we can do calculus inside that space. Understanding topology is probably the most rewarding experience in math.</p><h3>Scalar (dot) product</h3><p>The scalar product between two real <strong>n</strong>-dimensional vectors <strong>x</strong> and <strong>y</strong> is defined as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/470/1*L6rpwEgNmmJ0_eAY55K-1Q.png" /></figure><p>What makes this concept interesting is orthogonality. We know that two vectors are orthogonal if and only if their scalar product is <strong>0</strong>. Also, a vector is of unit length if its scalar product with itself is <strong>1</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*WPPOn4bV_Am4wfkTNeaWXw.jpeg" /><figcaption><strong>2</strong>-dimensional vectors <strong>u2</strong> and <strong>v2</strong> are orthogonal and of unit length (orthonormal).</figcaption></figure><p>If we have orthonormal vectors <strong>e1, …, en</strong> spanning our vector space, then</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/625/1*9xhAST37iyIi3cc-ri7TYA.png" /></figure><p>So, any given vector <strong>q</strong> can be expressed as a linear combination of those vectors. And the coefficients of those vectors are easily computable.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/464/1*4prg8DcpfSNJVBlEdd_vxw.png" /><figcaption>linear expansion of vector <strong>(1,2,3,4)</strong> along the standard 4d vector space basis.</figcaption></figure><p>How do we generalize this? It turns out the following axioms are a good choice to characterize the scalar product</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/449/1*rCRFR-C9XFp4UfaUGWGiVw.png" /><figcaption>Here <strong>α</strong> is a real number and <strong>x</strong>, <strong>y</strong>, <strong>z</strong> vectors.</figcaption></figure><p>Wouldn’t it be just insane if we extended this concept to functions? We can define the scalar product as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/365/1*00FG8GPnvaQcbVBWiArxWQ.png" /><figcaption>For some fixed <strong>a &lt; b</strong>.</figcaption></figure><p>As the integral is a generalization of the sum, we can see how this naturally generalizes our usual scalar product. This produces one of the most beautiful theories in math. Fourier’s theory. You may know the Fourier transform of a given function <strong>f</strong>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/558/1*Tm-oU2yD2QYhc8RMEF3ofQ.png" /></figure><p>This is a direct result of the vectors</p><blockquote>1=cos(0x), cos(nx), sin(nx) for n = 1, 2, 3, …</blockquote><p>being orthonormal in the above scalar product. And they span some vector space, including a large class of functions. So we can linearly expand those functions along our vectors, as we did in the non-generalized case, and get the formula for our coefficients:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/269/1*RoHhL6uFzGatmqHJf6R2sQ.png" /></figure><p>It’s also possible to find other sets of orthonormal vectors spanning the same space (such as <a href="https://en.wikipedia.org/wiki/Legendre_polynomials">Legendre polynomials</a>).</p><h3>Measure</h3><p>We understand how to measure an interval or the volume of some 3d object. E.g. for <strong>a ≤ b</strong> we have</p><blockquote>m([a, b]) = b - a</blockquote><p>It’s incredibly useful to generalize this concept. The whole mathematical basis for probability and statistics relies on this. So, what should a measure be?</p><p>We define it as a function that maps subsets of a given set to positive real numbers. It must satisfy the following conditions:</p><ul><li>a measure of the empty set is <strong>0</strong>,</li><li>if sets <strong>A </strong>and <strong>B </strong>contain different elements, then <strong>m(A ∪ B) = m(A) + m(B)</strong>. This should also hold for countable unions of such sets (then we have an infinite sum).</li></ul><p>A set is countable if its set size is equal to that of all integers. It’s crucial to this theory that the set of real numbers is strictly larger than the set of integers.</p><p>The second point gives us a way to measure separated sets separately:</p><blockquote><strong>m([1, 2]</strong> <strong>∪ [10, 11]) = m([1, 2]) + m([10, 11]).</strong></blockquote><p>What’s a measure in probability theory? Probability! We define probability as a measure on the space of all events. It takes a set of events and tells us their weight. E.g. to get the probability of a die rolling a two, we make our probability measure the weight of all possible current conditions (events) that lead to a world, where our die lands on a two.</p><p>In this way, the first step in mathematically defining probability is admitting that randomness doesn’t exist. We operate under an illusion of the existence of a set that perfectly describes all possible current conditions of our world. Any element (event) of that set is a specific condition and from it, the entire future can be predicted.</p><p>Others may have different interpretations of what events represent, but this intuition served me well in my numerous probability courses. And it’s philosophically intriguing, as we include reality being deterministic in our assumption, meaning our ignorance is the only thing making the world seem random.</p><h3>Conclusion</h3><p>After doing math for some time, your mind generalizes problems as soon as it interprets them. It’s a pattern, burned into your subconsciousness. When you encounter a problem your first thought is how to deconstruct it via generalization. In this way, you focus on only what’s important and abstract other bad things away.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=554aa6d7a821" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Two ‘proofs’ that the sum of all positive integers is -1/12]]></title>
            <link>https://nseverkar.medium.com/two-proofs-that-the-sum-of-all-natural-numbers-is-1-12-a317217bb8b9?source=rss-eadd94c100f7------2</link>
            <guid isPermaLink="false">https://medium.com/p/a317217bb8b9</guid>
            <category><![CDATA[paradox]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[math]]></category>
            <category><![CDATA[numbers]]></category>
            <dc:creator><![CDATA[kuco23]]></dc:creator>
            <pubDate>Thu, 31 Mar 2022 00:12:12 GMT</pubDate>
            <atom:updated>2022-05-01T14:43:10.413Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*vhLGkXrXSOIgUfsDGlBjiQ.jpeg" /></figure><p>You might have already heard this ‘fact’ somewhere. My city even had the equation as a part of its Christmas decoration (lighted up and everything). It turns out what we got for Christmas was lies.</p><p>By our definitions of limits (and everything else), the sum equals infinity. As you’d expect. Regardless, there are some connections between the sum and <strong>-1/12</strong>. They might look like proofs to an untrained eye, but are really just connections.</p><h3>Proof one</h3><p>Let’s define the following sum</p><blockquote>A = 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + …</blockquote><p>and look at its partial sums. If we add the first two terms, we get <strong>0</strong>, then we add <strong>1</strong> and get <strong>1</strong>, then it’s <strong>0</strong> again, then <strong>1</strong>, … So, this infinite sum is the limit of the sequence</p><blockquote>1, 0, 1, 0, 1, 0, 1, 0, 1, …</blockquote><p>What would be the most natural way to define this limit? Taking averages gets us</p><blockquote>1, 1 / 2, 2 / 3, 2 / 4, 3 / 5, 3 / 6, …</blockquote><p>This sequence converges to <strong>½</strong>, so I guess it would make sense to say that our initial sequence limits to <strong>½</strong>, meaning<strong> A = ½</strong>.</p><p>For the sum</p><blockquote>B = 1 - 2 + 3 - 4 + 5 - 6 + 7 - 8 + …</blockquote><p>we can notice that</p><blockquote>2 B =</blockquote><blockquote>= 1 - 2 + 3 - 4 + 5 - 6 + 7 - 8 + …</blockquote><blockquote>+ 0 + 1 - 2 + 3 - 4 + 5 - 6 + 7 - … =</blockquote><blockquote>= 1 - 1 + 1 - 1 + 1 - 1 + 1 - 1 + … =</blockquote><blockquote>= A</blockquote><p>So <strong>B = A / 2 = 1 / 4</strong>.</p><p>If we take our sum of all natural numbers</p><blockquote>S = 1 + 2 + 3 + 4 + 5 + 6 + …</blockquote><p>then</p><blockquote>S - B =</blockquote><blockquote>= 1 + 2 + 3 + 4 + 5 + 6 + … -</blockquote><blockquote>- 1 + 2 - 3 + 4 - 5 + 6 - … =</blockquote><blockquote>= 0 + 4 + 0 + 8 + 0 + 12 + … =</blockquote><blockquote>= 4(1 + 2 + 3 + …) = 4 S.</blockquote><p>We got<strong> 3S = -B = -1/4</strong>, which gives</p><blockquote>S = - 1 / 12.</blockquote><p>So, if your friend out of nowhere decides to one day give you a dollar and the next day two, then three, … End that toxic relationship and sue him for stealing. Use the above proof in court.</p><p>But seriously, these kinds of manipulations with divergent sums are forbidden in math, as you can quickly get contradictions. E.g.</p><blockquote>E = 1 + 1 + 1 + 1 + 1 + 1 + …</blockquote><blockquote>0 = E - E =</blockquote><blockquote>= 1 + 1 + 1 + 1 + 1 + 1 + 1 + … -</blockquote><blockquote>- 0 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - … =</blockquote><blockquote>= 1 + 0 + 0 + 0 + 0 + 0 + 0 + 0 = 1.</blockquote><p>Apparently, this was proof zero.</p><h3>Proof two</h3><p>This one uses some complex analysis. Maybe you have heard of the Riemann zeta function. It’s a pretty important function and finding its zeroes is a <a href="https://en.wikipedia.org/wiki/Riemann_hypothesis">problem worth a million bucks</a>. Its definition is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SGAyPnwYodOr5FVEu__pOA.png" /></figure><p>where <strong>s </strong>can also be a complex number. The thing with complex functions is that they can sometimes be incredibly nice. So nice, that knowing their values inside any disk on the complex plane, gives us exactly one natural extension on some larger area, like e.g. the whole complex plane.</p><p>The Riemann zeta function is really nice when the real part of <strong>s </strong>is larger than <strong>1</strong>. This gives us enough information to extend it to the whole complex plane. This is called analytic continuation. And it turns out that this continuation evaluated at <strong>s = -1</strong> gives us <strong>-1/12</strong>.</p><p>We formally can’t just plug <strong>s = - 1 </strong>in the sum on the right as that notation does not preserve analytic continuation. But it is very interesting that in this complex world, <strong>-1/12</strong> is the only natural definition for the sum of all natural numbers.</p><h3>Conclusion</h3><p>Don’t believe anyone who tries to convince you that any of the above arguments is actual proof (unless his math has some freaky definitions). Though if you are disappointed, math has a bunch of real paradoxes that may be as strange as this one.</p><p><a href="https://nseverkar.medium.com/the-most-controversial-axiom-in-mathematics-and-its-paradoxes-2c0cdfd725cb">The most controversial axiom in mathematics and its paradoxes</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a317217bb8b9" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How one infinite sum equals every number]]></title>
            <link>https://nseverkar.medium.com/why-we-cant-change-the-summation-order-of-an-infinite-sum-a99a6aaf39f9?source=rss-eadd94c100f7------2</link>
            <guid isPermaLink="false">https://medium.com/p/a99a6aaf39f9</guid>
            <category><![CDATA[paradox]]></category>
            <category><![CDATA[education]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[math]]></category>
            <dc:creator><![CDATA[kuco23]]></dc:creator>
            <pubDate>Tue, 29 Mar 2022 01:59:04 GMT</pubDate>
            <atom:updated>2022-06-28T18:01:21.581Z</atom:updated>
            <content:encoded><![CDATA[<h4>Understanding a mathematical paradox</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/612/1*W5bh0zk3jwnlAJjHzsSk2w.jpeg" /><figcaption>Photo by <a href="https://www.istockphoto.com/portfolio/benjaminec?mediatype=photography">benjaminec</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>The rule for commutativity of addition is <strong>a + b = b + a</strong>. It makes sense, as it shouldn’t matter in what order we count certain objects. All that matters is that we count them all exactly once. If you feel extremely sadomasochistic today, you can check <a href="https://medium.com/p/8b5549f1cf9c">this</a> formal proof.</p><p>Inductively, commutativity can be extended to</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FtvEXMXk2rCIz-k8YpOssQ.png" /></figure><p>where <strong>σ </strong>is any permutation (summation order). It might seem we could also extend this to infinite sums. Well, it turns out we can’t. Not only that, but one sum can evaluate to any real number, depending on its summation order. This post is about understanding why that happens.</p><p>We define an infinite sum as a limit of partial sums:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*I94H-Kx7lSw11wOf2pjWRQ.png" /></figure><p>First, we’ll show that the sum</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/454/1*DPwbpU3_UxA7fuHqCz1FzQ.png" /></figure><p>can attain values ∞ and -∞, depending on the order of our summation. You’ll have to take my word (or read <a href="https://web.williams.edu/Mathematics/lg5/harmonic.pdf">this</a> short proof), that taking the positive and the negative parts of the sum, gets us</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/395/1*RjXn5QvXoQnuK-0m24jHuQ.png" /></figure><p>If for any number <strong>n</strong>, we take away the first <strong>n</strong> terms from either of the above sums, we have taken away a finite sum, therefore subtracted a finite number. Because this does not affect infinity, we get</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/591/1*7KIL-VXRVrI7lrs3vIgtIg.png" /><figcaption>previous sums with the first <strong>n </strong>terms taken away.</figcaption></figure><p>By the definition of an infinite sum being equal to ∞, we have that for arbitrarily large numbers <strong>x</strong>, we can take some finite amount of terms away from the sum and add them up into a number bigger than <strong>x</strong>.</p><p>But us taking away those terms didn’t affect infinity one bit. So we can do the exact same thing again to make our remaining terms produce yet another arbitrarily large number.</p><p>Let’s describe the order in which we sum up our initial infinite sum. We’ll iteratively sum up terms from the positive and negative parts, adding them to our partial sum.</p><ul><li>Add (finitely many) terms from the positive part of the sum, so that the partial sum will be larger than <strong>1 + 1/2</strong>.</li><li>Add the first negative term <strong>-1/2</strong>. Our partial sum is now larger than <strong>1</strong>.</li><li>Add (finitely many) remaining terms from the positive part of the sum, so that the partial sum will be larger than <strong>2 + 1/4</strong>.</li><li>Add the second negative term <strong>-1/4</strong>. Our partial sum is now larger than <strong>2</strong>.</li><li>Add (finitely many) remaining terms from the positive part of the sum, so that the partial sum will be larger than <strong>3 + 1/6.</strong></li><li>Add the third negative term <strong>-1/6</strong>. Our partial sum is now larger than <strong>3</strong>.</li><li>…</li></ul><p>See that for every added negative number, we pick a huge amount of positive numbers to balance it off. Because of this, our partial sum goes to infinity.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4eea803887f93310d170ad1acd21a71e/href">https://medium.com/media/4eea803887f93310d170ad1acd21a71e/href</a></iframe><p>A very important observation is that every term of our initial sum is eventually added up by this process (meaning we really shuffle the order of addition). This depends on us always having enough positive terms to produce arbitrarily large numbers.</p><p>If we wanted our sum to be -∞, the process would be completely symmetric. With a little more effort we can make the sum evaluate to any real number.</p><p>We use the fact that our terms <strong>1 / n</strong> go to <strong>0</strong>, so we can add up smaller and smaller numbers, which makes it possible to achieve arbitrarily precise approximations of our chosen limit.</p><p>Choose any <strong>r </strong>and proceed similarly as before:</p><ul><li>Add up terms from the positive part and stop immediately when the partial sum becomes (strictly) larger than <strong>r</strong>.</li><li>Add up terms from the negative part and stop immediately when the partial sum becomes (strictly) smaller than <strong>r</strong>.</li><li>Continue adding the remaining terms from the positive part and stop immediately when the partial sum becomes (strictly) larger than <strong>r</strong>.</li><li>Continue adding the remaining terms from the positive part and stop immediately when the partial sum becomes (strictly) smaller than <strong>r</strong>.</li><li>…</li></ul><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/11e360aeb9722466a54df0109b6d7b4a/href">https://medium.com/media/11e360aeb9722466a54df0109b6d7b4a/href</a></iframe><p>In each step, we have to add at least one term to jump from strictly under <strong>r</strong> to strictly over<strong> r</strong> (or vice-versa). So, after <strong>n</strong> steps of the above process, all the remaining terms are smaller than <strong>1 / n</strong>. Is it then possible for our partial sum to leave the interval</p><blockquote>[r - 1 / n, r + 1 / n] ?</blockquote><p>Let’s split two cases:</p><ul><li>If we are below <strong>r</strong>, then we can’t suddenly jump to something larger than<strong> r + 1 / n</strong>, as we’re adding a term smaller than <strong>1 / n</strong>.</li><li>If we are above <strong>r</strong>, then we can’t jump to something smaller than<strong> r - 1 / n</strong>, as we’re subtracting a term smaller than <strong>1 / n</strong>.</li></ul><p>Thus our partial sum will remain in the above interval for all steps after <strong>n</strong>. When we send <strong>n</strong> to infinity, we have that the partial sum will close in on <strong>r</strong>. This means that our infinite sum, with the constructed order of summation, will equal <strong>r</strong>.</p><blockquote>The value of the sum, with terms ordered as we’ve written them, is <strong>log(2)</strong>.</blockquote><h3>Conclusion</h3><p>We saw that relying on intuition doesn’t always work in math. Many paradoxes show us how math is not completely aligned with our adaptation to reality. It’s a perfectionist’s view of reality. And understanding those kinds of paradoxes through subtleties is what makes it fun.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a99a6aaf39f9" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Proofs your teacher should have taught you]]></title>
            <link>https://nseverkar.medium.com/proofs-that-your-teacher-should-have-taught-you-1e3de9be2d87?source=rss-eadd94c100f7------2</link>
            <guid isPermaLink="false">https://medium.com/p/1e3de9be2d87</guid>
            <category><![CDATA[math]]></category>
            <category><![CDATA[science]]></category>
            <category><![CDATA[derivatives]]></category>
            <category><![CDATA[teaching]]></category>
            <category><![CDATA[mathematics]]></category>
            <dc:creator><![CDATA[kuco23]]></dc:creator>
            <pubDate>Fri, 18 Mar 2022 22:57:43 GMT</pubDate>
            <atom:updated>2022-05-28T20:50:24.969Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jnGfjHuXjoNaCoAFgTUnkA.jpeg" /></figure><p>For as long as I can remember, I had issues remembering new information. But at about 8, I discovered that if the information could be derived by some logical steps, I could remember those very well.</p><p>In high school, mathematics was done in what I now recognize as a very non-mathematical way. We were told to dogmatically memorize formulas and laws, so I struggled with many tests and got bad grades. That was until I realized what math truly was. It wasn’t about memorizing stuff, it was about understanding it.</p><p>Suddenly everything became simple. Apart from the few definitions, I derived pretty much everything and optimized my brain’s storage space. And later, at the university, this way of studying has turned out to be the right one.</p><p>This post is about clearing up some easy proofs that most teachers skip. They’re not difficult but can open a door to studying mathematics the way it was meant to be studied.</p><h4>Arithmetic sums</h4><p>Let’s consider the following sum</p><blockquote>s(n) = 1 + 2 + 3 + 4 + 5 + 6 + … + (n-1) + n.</blockquote><p>Its simplification is based on one easy step, discovered by an 8-year old (ok, <a href="https://en.wikipedia.org/wiki/Carl_Friedrich_Gauss">he</a> was a genius). The step is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PltNFhui4_NOyMn9vdmx7w.png" /></figure><p>We have to notice that adding the same colors always results in <strong>(n+1)</strong>. Finally, dividing by <strong>2 </strong>gives us</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/253/1*DhGFOBL9mxb9lwPRTVyZrQ.png" /></figure><p>At this point, deriving the generalized arithmetic sum is trivial:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/892/1*ks8ZtZQBQ4c_-D8XuILcVQ.png" /></figure><h4>Geometric sums</h4><p>For a given number <strong>q</strong>, the geometric sum is of the form</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/396/1*7turdfxpmQnVrq8mUpakbw.png" /></figure><p>I remember my teacher telling me that deriving the formula was complicated. It’s weird thinking about how easily I accepted this ‘fact’. When I eventually did find out the derivation, it was incredibly easy and in a way beautiful:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*arIW-WelYYOK4aStc61ljw.png" /></figure><p>The trick is to notice that the same colors cancel out. To finish, we divide by <strong>(1 - q)</strong> on both sides:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/569/1*AWSXXYAJrmRhFmoDorijdw.png" /></figure><p>I always forget the above formula, while the idea of multiplying the geometric sum into a nicer form is engraved in my mind forever. It’s so natural!</p><p>Chances are, you’ve also encountered the below formula for the<strong> infinite</strong> geometric sum</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/442/1*NZVWz_bwTOPDfSQs3yxS8g.png" /></figure><p>As this is the limit of the previous sum (<strong>n </strong>goes to infinity), you can see exactly how it’s derived and therefore what condition <strong>q</strong> must satisfy (<strong>|q| &lt; 1</strong>) for it to hold.</p><h4>Chain rule</h4><p>Most people will recognize the chain rule:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/382/1*hykaZ7KfUXhoazGqKHUq1Q.png" /></figure><p>Unfortunately, few have seen how it’s derived. The derivation reveals that math is not just about reducing expressions. Expansions can often be extremely useful. In the below proof, we add two terms that cancel each other, in order to obtain the rule:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/799/1*uXGnNkj6X9QY9yAm_ew5Lg.png" /></figure><p>We’ve used that the limit of a product is a product of two limits (if they both exist). This proof works in most cases but overall has a (removable) flaw, which is discussed in the comment section.</p><h4>Product rule</h4><p>As with the chain rule, this one should also look familiar:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/516/1*0JAX4oNPzol8vstOAPrGtQ.png" /></figure><p>Its proof is similar to that of the chain rule, except now we expand the expression by adding two terms that add up to zero:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jI7tATkS9WZPFPElBB9OKg.png" /></figure><p>We used the fact that <strong>+</strong> and <strong>×</strong> can be taken outside the limits.</p><h4>Power rule</h4><p>We all know the derivative of the following function.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/233/1*pdSd9pkl-dEDhwQ3_U396g.png" /></figure><p>Let’s learn how to prove it. By definition of the derivative, we have</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/351/1*M0-b6iExXIq52bs-txsnbg.png" /></figure><p>It will be helpful to generalize the previous result from the geometric sums section:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jBqC6SDEbzPUXS5Gpg-BEw.png" /></figure><p>Again, the same colors cancel out. Now switch <strong>x</strong> for <strong>a</strong> and <strong>x0 </strong>for<strong> b </strong>to get</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Mtz7u0R5dqsccsbgov80cg.png" /></figure><p>You may have noticed that our derivation also holds for all real exponents <strong>k</strong> and complex numbers<strong> x</strong>. So we’ve proven quite a lot:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/328/1*eJfRly0TmyyzYPGNOJOvYw.png" /></figure><h3>Conclusion</h3><p>Memorizing formulas is tedious and many wrongly associate it with math. Math is about understanding things. There are formulas in mathematics that no living soul could possibly remember, while their derivation is natural and can be done with some effort. All you have to do is think for yourself and not let people tell you to just accept mathematical statements. Ask them why.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/596/1*4EbWL0vVb_7J76mFdaq3MQ.png" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1e3de9be2d87" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Why there’s always a larger infinity]]></title>
            <link>https://nseverkar.medium.com/for-every-infinity-there-exists-a-bigger-infinity-47c7a3a8f420?source=rss-eadd94c100f7------2</link>
            <guid isPermaLink="false">https://medium.com/p/47c7a3a8f420</guid>
            <category><![CDATA[set-theory]]></category>
            <category><![CDATA[infinity]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[logic]]></category>
            <dc:creator><![CDATA[kuco23]]></dc:creator>
            <pubDate>Tue, 15 Mar 2022 15:44:36 GMT</pubDate>
            <atom:updated>2022-06-28T18:12:07.957Z</atom:updated>
            <content:encoded><![CDATA[<h4>Understanding the mathematical view of infinity</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*_RnvhVuBo018WP4taE7e8A.png" /></figure><p>This post is about one formal notion of infinity in mathematics. Using that notion, we’ll see that there are infinitely many different infinities and that for every infinity there exists a larger infinity.</p><h3>Sets and infinity</h3><p>A set is one of the most important concepts in mathematics. It describes our classification of certain objects. And it does that without caring about the order of its elements or their repetitions. For example</p><blockquote>{2, 5, 9, 1}, {x, y, z}, {{1, 2}, {x}}, {0.123, 2.3, π} and {}</blockquote><p>are all sets and</p><blockquote>{2, 5, 5, 5, 3, 3} = {2, 5, 3} = {5, 3, 2} = {5, 2, 2, 3}.</blockquote><p>We say that <strong>A</strong> is a subset of <strong>B</strong> if <strong>B</strong> contains all elements of <strong>A</strong>. For example, given the set <strong>X = {0,1,2}</strong>, we have the set of all its subsets</p><blockquote>𝒫(X) = {{}, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}.</blockquote><p>Here, <strong>𝒫(X)</strong> is called the power set of <strong>X</strong>. Note that we also include the empty set <strong>{}</strong>, as the empty set is a subset of every set.</p><p>All of the above sets are finite. An example of an infinite set would be</p><blockquote>ℕ = {0, 1, 2, 3, 4, 5, 6, …}.</blockquote><p>This is called the set of natural numbers. Its existence is not proved but axiomatized (by the <a href="https://en.wikipedia.org/wiki/Axiom_of_infinity">axiom of infinity</a>). In other words, infinity doesn’t necessarily exist, we have to believe it does.</p><p>Why should we believe? Well, it’s an incredibly useful concept. Without it, embarrassingly little mathematics could be done. More or less, every contribution of maths to physics depends on this axiom. So, for the sake of physics, let’s believe.</p><h3>How to compare set sizes?</h3><p>We are used to counting the number of elements in a given set and then comparing the numbers themselves. That is not a useful definition in our case, as we want to compare infinite sets. Luckily, there exists a more natural definition for set comparison.</p><p>We should be able to say that the set <strong>{0,1}</strong> is smaller than <strong>{0,1,2}</strong>. That’s obvious as <strong>{0,1}</strong> is a subset of <strong>{0,1,2}</strong>. Can we just define “smaller” by “is a subset”?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/225/1*ZjR4txqe9a5O5wrUM9KDvw.jpeg" /></figure><p>What about <strong>{5,6}</strong> and <strong>{0,1,2}</strong>. Again we want to say that <strong>{5,6}</strong> is a smaller set than <strong>{0,1,2}</strong>, but now we can’t use the previous definition.</p><p>What we do is rename <strong>5 ↦ 0 </strong>(<strong>5 </strong>to <strong>0</strong>) and <strong>6 ↦ 1</strong> (<strong>6 </strong>to <strong>1</strong>). Formally, this is a one-to-one mapping from <strong>{5,6} </strong>to<strong> {0,1,2}. </strong>One-to-one means it assigns a unique value (name) to each element.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/361/1*4YjHcTjehn9anR_77mflgg.jpeg" /><figcaption>A one-to-one mapping.</figcaption></figure><p>We say that set <strong>A</strong> is smaller than set <strong>B</strong> if there exists a one-to-one function, mapping elements in <strong>A </strong>to elements in <strong>B</strong>. Why is this a good definition? Because it’s also defined for infinite sets.</p><p>We also have to define the equality of set sizes. This is done by requiring a function to be more than just one-to-one. It should also reach every value in the corresponding set. A function satisfying those two properties is called a bijection.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/306/1*UKE4pb6wXckDb1WRf5rf_A.jpeg" /><figcaption>A bijective mapping.</figcaption></figure><p>We say that sets <strong>A</strong> and <strong>B</strong> are of equal size when there exists a bijection from <strong>A</strong> to <strong>B</strong>. Intuitively this means that every element <strong>a</strong> in <strong>A</strong> has exactly one corresponding element <strong>b</strong> in <strong>B</strong>, and vice-versa (as in the above picture).</p><p>To convince you of the naturalness of this definition, we have to look at how our brains count things. Let’s say I ask you to count the number of the following intervals.</p><blockquote>[0, 1], [1, 2], [2, 3], … , [n-1, n].</blockquote><p>Chances are, you’ll map <strong>i ↦ [i-1, i]</strong> and see that sending <strong>i </strong>from <strong>1</strong> to <strong>n </strong>generates all the intervals, encountering each one exactly once. So, you have constructed a bijection between the set <strong>{1, 2, 3, …, n} </strong>and those intervals. Our brain chooses this set because it’s the most natural representation of a number<strong> n</strong>.</p><p>Counting infinities using our definition is not always entirely intuitive. For example, even numbers form a strict subset of natural numbers. But according to our definition, they are of the same size, as</p><blockquote>x <strong>↦ </strong>x / 2</blockquote><p>is a bijection, mapping even numbers to natural numbers.</p><p>There are more extreme cases though. It turns out the set of rational numbers (fractions) is the same size as the set of natural numbers.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/454/1*R6A2kVze-iDL0E0fJObHVw.png" /><figcaption>An enumeration of rational numbers by the natural numbers.</figcaption></figure><p>Given sets <strong>A </strong>and <strong>B</strong>, you may have thought about defining their size-equality by requiring <strong>A</strong> to be smaller than <strong>B</strong> and <strong>B</strong> to be smaller than <strong>A</strong>. That means requiring the existence of two one-to-one functions: one from <strong>A </strong>to <strong>B </strong>and another from <strong>B </strong>to <strong>A</strong>. That’s also a natural definition and it turns out to be equivalent to ours. This is <a href="https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstein_theorem">not a trivial result</a> though.</p><h3>Every set is strictly smaller than its power set</h3><p>Let’s pick any set <strong>X</strong>. Immediately it is obvious that <strong>X</strong> is smaller than <strong>𝒫(X)</strong>, as</p><blockquote><strong>x ↦ {x}</strong></blockquote><p>is a one-to-one function, mapping from <strong>X</strong> to <strong>𝒫(X)</strong>. To show that <strong>X</strong> is strictly smaller than <strong>𝒫(X)</strong>, we need to prove that they are not of equal size. So we should prove that there are no bijections between <strong>X </strong>and <strong>𝒫(X)</strong>.</p><p>Proving this was a great mathematical achievement (done by Georg Cantor in 1891) and we’re going to show how it was done.</p><p>What if such a bijection was to exist? Let’s assume it does! So, we have a bijection <strong>e</strong>, mapping from <strong>X</strong> to <strong>𝒫(X)</strong>. We define the set of elements <strong>x</strong> inside <strong>X</strong>, for which it holds that <strong>x</strong> does not belong to the set <strong>e(x)</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/286/1*ZvWZWIFboRO1zoJqUC6OqQ.png" /></figure><p>Because this is a subset of <strong>X </strong>(so a member of the power set <strong>𝒫(X)</strong>), we need to have <strong>S = e(s)</strong> for some <strong>s</strong>, as <strong>e</strong> is a bijection between <strong>X </strong>and <strong>𝒫(X)</strong>. Now we ask if <strong>s</strong> is in <strong>S</strong>:</p><ul><li>if <strong>s ∈ S</strong>, then by definition <strong>s ∉ e(s) = S</strong>,</li><li>if <strong>s ∉ S</strong>, then again by definition<strong> s ∈ e(s) = S</strong>.</li></ul><p>What? How could this happen? That’s a contradiction! Exactly! We are in contradiction with our only assumption, that being the existence of a bijection <strong>e</strong>. This means we can’t have any bijection between <strong>X</strong> and <strong>𝒫(X)</strong>. End of proof.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*V4b7EhrpEpNqJzOYIYu17g.jpeg" /></figure><p>The self-referential nature of this argument may have been hard to follow. If you want to know more about this argument and how it’s used in math, <a href="https://medium.com/p/53dca529570e">here</a> is a post on its generalization.</p><h3>Aleph numbers</h3><p>We have identified an infinite number of infinities</p><blockquote>ℕ, <strong>𝒫</strong>(ℕ), <strong>𝒫</strong>(<strong>𝒫</strong>(ℕ)), <strong>𝒫</strong>(<strong>𝒫</strong>(<strong>𝒫</strong>(ℕ))), …</blockquote><p><a href="https://en.wikipedia.org/wiki/Aleph_number">Aleph numbers</a> are a naming convention for infinite sizes. They are denoted by</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/428/1*HGpzk0l0mTwsWXEpKRHNbA.png" /></figure><ul><li><strong>ℵ0</strong> represents the smallest infinity (it turns out this is the size of <strong>ℕ</strong>),</li><li><strong>ℵ1</strong> represents the smallest infinity that is larger than <strong>ℵ0</strong>,</li><li><strong>ℵ2</strong> represents the smallest infinity that is larger than <strong>ℵ1</strong>,</li><li>…</li></ul><p>It was <a href="https://plato.stanford.edu/entries/continuum-hypothesis/">conjectured</a> that <strong>ℵ1 </strong>is the size of the set <strong>𝒫(ℕ)</strong> but later proven that standard mathematics is not strong enough to prove or disprove this (using the <a href="https://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory">axioms of set theory</a>).</p><p>From our previous enumeration of aleph numbers, you might have concluded them to be enumerated by natural numbers. The truth is, they are way more complex. They can even enumerate themselves.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/425/1*CvFHueFInVFGdhkC1c6slw.png" /></figure><p>So the fun never ends!</p><h3>Usages of our result</h3><p>When I was 8, we argued in simple ways. The one who expressed his argument’s strength with a higher number, won. A way to circumvent this was to use infinity. But I’m an adult now and I use math in my arguments.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BNLkAfwCk8lBua8LS6HlEA.png" /></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=47c7a3a8f420" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>