Skip to content

Instantly share code, notes, and snippets.

@james-d-mitchell

james-d-mitchell/tropical-one-relation-monoids.ipynb

Created October 1, 2022 13:36
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save james-d-mitchell/cec4ef0a74259ff9dddf6e106c084f99 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save james-d-mitchell/cec4ef0a74259ff9dddf6e106c084f99 to your computer and use it in GitHub Desktop.
Download ZIP
TROPICAL ONE-RELATION MONOIDS
Display the source blob
Display the rendered blob
Raw
tropical-one-relation-monoids.ipynb
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"provenance": [],
"collapsed_sections": [],
"authorship_tag": "ABX9TyPBBEkUm8d2lEtpq8fJAAXQ",
"include_colab_link": true
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3"
},
"language_info": {
"name": "python"
}
},
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "view-in-github",
"colab_type": "text"
},
"source": [
"<a href=\"https://colab.research.google.com/gist/james-d-mitchell/cec4ef0a74259ff9dddf6e106c084f99/tropical-one-relation-monoids.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
]
},
{
"cell_type": "markdown",
"source": [
"Verifying some claims in https://arxiv.org/pdf/2209.12612.pdf"
],
"metadata": {
"id": "ZyT3oY2XfMyT"
}
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "BookauPDeYn8",
"outputId": "11ee0445-9d3f-4d6b-e8e5-7c7ebc6a159d"
},
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
"Requirement already satisfied: libsemigroups_pybind11 in /usr/local/lib/python3.7/dist-packages (0.3.0)\n",
"Requirement already satisfied: pkgconfig>=1.5.0 in /usr/local/lib/python3.7/dist-packages (from libsemigroups_pybind11) (1.5.5)\n",
"Requirement already satisfied: pybind11>=2.6 in /usr/local/lib/python3.7/dist-packages (from libsemigroups_pybind11) (2.10.0)\n",
"Requirement already satisfied: packaging>=20.4 in /usr/local/lib/python3.7/dist-packages (from libsemigroups_pybind11) (21.3)\n",
"Requirement already satisfied: pyparsing!=3.0.5,>=2.0.2 in /usr/local/lib/python3.7/dist-packages (from packaging>=20.4->libsemigroups_pybind11) (3.0.9)\n",
"Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
"Collecting wurlitzer\n",
" Downloading wurlitzer-3.0.2-py3-none-any.whl (7.3 kB)\n",
"Installing collected packages: wurlitzer\n",
"Successfully installed wurlitzer-3.0.2\n"
]
}
],
"source": [
"! pip install libsemigroups_pybind11\n",
"! pip install wurlitzer\n",
"%load_ext wurlitzer"
]
},
{
"cell_type": "code",
"source": [
"from libsemigroups_pybind11 import KnuthBendix, ReportGuard\n",
"from datetime import timedelta\n",
"rg = ReportGuard(True)\n",
"K = KnuthBendix()\n",
"K.set_alphabet(\"ba\")\n",
"K.add_rule(\"abba\", \"\")\n",
"K.run_for(timedelta(seconds=10))"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "QZldSU8Meazw",
"outputId": "8c29ff39-e341-44ad-dd24-50f11a8fb46c"
},
"execution_count": 10,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"#0: KnuthBendix: running for approx. 10000ms\n",
"#0: KnuthBendixImpl: active rules = 300, inactive rules = 0, rules defined =\n",
" 1781\n",
"#0: KnuthBendixImpl: active rules = 380, inactive rules = 0, rules defined =\n",
" 2261\n",
"#0: KnuthBendixImpl: active rules = 436, inactive rules = 0, rules defined =\n",
" 2597\n",
"#0: KnuthBendixImpl: active rules = 480, inactive rules = 1, rules defined =\n",
" 2866\n",
"#0: KnuthBendixImpl: active rules = 517, inactive rules = 0, rules defined =\n",
" 3083\n",
"#0: KnuthBendixImpl: active rules = 547, inactive rules = 1, rules defined =\n",
" 3264\n",
"#0: KnuthBendixImpl: active rules = 576, inactive rules = 0, rules defined =\n",
" 3437\n",
"#0: KnuthBendixImpl: active rules = 603, inactive rules = 0, rules defined =\n",
" 3599\n",
"#0: KnuthBendixImpl: active rules = 627, inactive rules = 1, rules defined =\n",
" 3745\n",
"#0: KnuthBendixImpl: stopping with active rules = 648, inactive rules = 1,\n",
" rules defined = 3874\n",
"#0: KnuthBendixImpl: elapsed time (knuth_bendix): 10000ms\n",
"#0: KnuthBendix: timed out!\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"K.confluent()"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "JSx4iGxqf2l_",
"outputId": "06e4cd46-a163-4193-e80c-ee5cf28516c5"
},
"execution_count": 11,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"False"
]
},
"metadata": {},
"execution_count": 11
}
]
},
{
"cell_type": "code",
"source": [
"K.finished()"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "977NYmBqf6df",
"outputId": "40b0e97b-ffb7-4fa2-9809-a26fdae92e48"
},
"execution_count": 4,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"False"
]
},
"metadata": {},
"execution_count": 4
}
]
},
{
"cell_type": "code",
"source": [
"K = KnuthBendix()\n",
"K.set_alphabet(\"ab\")\n",
"K.add_rule(\"ab\", \"\")\n",
"K.run_for(timedelta(seconds=10))"
],
"metadata": {
"id": "8gO4VbWOf7tO"
},
"execution_count": 12,
"outputs": []
},
{
"cell_type": "code",
"source": [
"K.confluent()"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "914cLyTBhK_C",
"outputId": "7280c80c-e46e-4f5d-b4c4-f824b690d3ab"
},
"execution_count": 13,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"execution_count": 13
}
]
},
{
"cell_type": "code",
"source": [
"K.size()"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "3vBpjXkqhMS1",
"outputId": "d1584f14-060c-4bb0-903e-00c795dc9de5"
},
"execution_count": 14,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"18446744073709551614"
]
},
"metadata": {},
"execution_count": 14
}
]
},
{
"cell_type": "code",
"source": [
"M5 = KnuthBendix()\n",
"M5.set_alphabet(\"ba\")\n",
"M5.add_rule(\"aba\", \"ba\")\n",
"M5.run_for(timedelta(seconds=10))"
],
"metadata": {
"id": "QNbCsRXnhNYQ"
},
"execution_count": 36,
"outputs": []
},
{
"cell_type": "code",
"source": [
"M5.number_of_active_rules() \n",
"M5.finished()"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "jOs3k9TJmF94",
"outputId": "f3437270-ed8b-4f84-d486-5f4c2a8cde52"
},
"execution_count": 38,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"False"
]
},
"metadata": {},
"execution_count": 38
}
]
},
{
"cell_type": "code",
"source": [
"def pow(A, e):\n",
" B = A\n",
" for _ in range(e - 1):\n",
" B = B * A\n",
" return B"
],
"metadata": {
"id": "Zw6D47lspkkY"
},
"execution_count": 60,
"outputs": []
},
{
"cell_type": "markdown",
"source": [
"Lemma 2.2"
],
"metadata": {
"id": "vvMVDS6SpEjq"
}
},
{
"cell_type": "code",
"source": [
"from libsemigroups_pybind11 import Matrix, MatrixKind\n",
"NEGATIVE_INFINITY = -2147483648\n",
"k = 5\n",
"A = Matrix(MatrixKind.MaxPlus, [[0, 1], \n",
" [NEGATIVE_INFINITY, 1]])\n",
"B = Matrix(MatrixKind.MaxPlus, [[0, 0], \n",
" [NEGATIVE_INFINITY, -1]])\n",
"(A * B) * A == A, (A * B) * B == B, A * (A * B) == A, B * (A * B) == B"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "I28txzqPpEH0",
"outputId": "768ddf10-e06c-4462-fab4-1c018347e07b"
},
"execution_count": 61,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"(True, True, True, True)"
]
},
"metadata": {},
"execution_count": 61
}
]
},
{
"cell_type": "code",
"source": [
"i, j = 10, 119\n",
"pow(B, i) * pow(A, j) == Matrix(MatrixKind.MaxPlus, [[0, j], [NEGATIVE_INFINITY, j - i ]])"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "g_sHzBYkqJjF",
"outputId": "278d7a59-920c-4e3c-d258-719cdaa8d6c6"
},
"execution_count": 63,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"execution_count": 63
}
]
},
{
"cell_type": "markdown",
"source": [
"Lemma 2.4"
],
"metadata": {
"id": "wIhbFW0Cq3dM"
}
},
{
"cell_type": "code",
"source": [
"from libsemigroups_pybind11 import Congruence, congruence_kind\n",
"M6 = Congruence(congruence_kind.twosided)\n",
"M6.set_number_of_generators(2)\n",
"M6.add_pair([0, 1], [1])\n",
"M6.number_of_classes()"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "jNwBuAOmq7F4",
"outputId": "e038a465-414d-4508-bb7b-af7853b81a0e"
},
"execution_count": 68,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"18446744073709551614"
]
},
"metadata": {},
"execution_count": 68
}
]
},
{
"cell_type": "code",
"source": [
"from libsemigroups_pybind11 import Matrix, MatrixKind\n",
"NEGATIVE_INFINITY = -2147483648\n",
"k = 5\n",
"A = Matrix(MatrixKind.MaxPlus, [[0, NEGATIVE_INFINITY], \n",
" [NEGATIVE_INFINITY, 1]])\n",
"B = Matrix(MatrixKind.MaxPlus, [[1, 1], \n",
" [NEGATIVE_INFINITY, NEGATIVE_INFINITY]])\n",
"A * B == B"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "DEE5C9EyrtOq",
"outputId": "47f8e073-f9c5-4da1-98e8-aa7ace7bed55"
},
"execution_count": 69,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"execution_count": 69
}
]
},
{
"cell_type": "code",
"source": [
"alpha, beta = 10, 7\n",
"pow(A, beta) == Matrix(MatrixKind.MaxPlus, [[0, NEGATIVE_INFINITY], \n",
" [NEGATIVE_INFINITY, beta]])"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "LXgsuukEsCCv",
"outputId": "a77c39bf-d22f-46cc-fcd1-271fe509f1ef"
},
"execution_count": 70,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"execution_count": 70
}
]
},
{
"cell_type": "code",
"source": [
"pow(B, alpha) == Matrix(MatrixKind.MaxPlus, [[alpha, alpha], \n",
" [NEGATIVE_INFINITY, NEGATIVE_INFINITY]])"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "Z0q81U-PsQFv",
"outputId": "583443f2-2798-4f09-f8aa-5dff59ae30e7"
},
"execution_count": 72,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"execution_count": 72
}
]
},
{
"cell_type": "code",
"source": [
"pow(B, alpha) * pow(A, beta) == Matrix(MatrixKind.MaxPlus, [[alpha, alpha + beta], \n",
" [NEGATIVE_INFINITY, NEGATIVE_INFINITY]])"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "s7mvzWmGsZH7",
"outputId": "9aaa9f2b-f707-4dd9-d232-f636eb82c82a"
},
"execution_count": 73,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"execution_count": 73
}
]
},
{
"cell_type": "markdown",
"source": [
"Lemma 2.5"
],
"metadata": {
"id": "3boIHLKehmcI"
}
},
{
"cell_type": "code",
"source": [
"from libsemigroups_pybind11 import Matrix, MatrixKind\n",
"NEGATIVE_INFINITY = -2147483648\n",
"k = 5\n",
"A = Matrix(MatrixKind.MaxPlus, [[k - 1, NEGATIVE_INFINITY], [NEGATIVE_INFINITY, 0]])\n",
"B = Matrix(MatrixKind.MaxPlus, [[1, 1], [NEGATIVE_INFINITY, NEGATIVE_INFINITY]])"
],
"metadata": {
"id": "g6SA1ikxhn7R"
},
"execution_count": 75,
"outputs": []
},
{
"cell_type": "code",
"source": [
"alpha, beta = 5, 7"
],
"metadata": {
"id": "WtDQ0_Iss8Tm"
},
"execution_count": 76,
"outputs": []
},
{
"cell_type": "code",
"source": [
"A * B == pow(B, 5)"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "mVgyRHI-htzL",
"outputId": "c66d87d9-97e5-4b48-f460-8733267e31fc"
},
"execution_count": 77,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"execution_count": 77
}
]
},
{
"cell_type": "code",
"source": [
"pow(B, alpha) * pow(A, beta) == Matrix(MatrixKind.MaxPlus, [[alpha + (k - 1) * beta, alpha], [NEGATIVE_INFINITY, NEGATIVE_INFINITY]])"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "I-Qqlfscj657",
"outputId": "bde89dc1-f319-4aa1-c6c7-44ce9ab43145"
},
"execution_count": 78,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"execution_count": 78
}
]
},
{
"cell_type": "markdown",
"source": [
"Lemma 2.6"
],
"metadata": {
"id": "fgbssIFMtaGi"
}
},
{
"cell_type": "code",
"source": [
"from libsemigroups_pybind11 import Matrix, MatrixKind\n",
"NEGATIVE_INFINITY = -2147483648\n",
"k = 5\n",
"A = Matrix(MatrixKind.MaxPlus, [[1, NEGATIVE_INFINITY], \n",
" [NEGATIVE_INFINITY, 0]])\n",
"B = Matrix(MatrixKind.MaxPlus, [[NEGATIVE_INFINITY, 1], \n",
" [NEGATIVE_INFINITY, 1]])\n",
"\n",
"B * A == B"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "Q8M_jevotZmn",
"outputId": "b2d80403-9821-4c28-9f0b-3ed10cb72bc5"
},
"execution_count": 83,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"execution_count": 83
}
]
},
{
"cell_type": "markdown",
"source": [
"Lemma 2.9"
],
"metadata": {
"id": "L4xBIh6hmZC1"
}
},
{
"cell_type": "code",
"source": [
"from libsemigroups_pybind11 import Matrix, MatrixKind\n",
"NEGATIVE_INFINITY = -2147483648\n",
"k = 5\n",
"A = Matrix(MatrixKind.MaxPlus, [[0, 1, NEGATIVE_INFINITY, 0], \n",
" [NEGATIVE_INFINITY, 1, 0, -1],\n",
" [NEGATIVE_INFINITY] * 4, \n",
" [NEGATIVE_INFINITY] * 4])\n",
"B = Matrix(MatrixKind.MaxPlus, [[1, 0, 0, -1], \n",
" [NEGATIVE_INFINITY] * 3 + [0],\n",
" [NEGATIVE_INFINITY] * 2 + [0] + [NEGATIVE_INFINITY], \n",
" [NEGATIVE_INFINITY] * 3 + [1]])\n",
"A, B"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "HhgAfGGLmaVC",
"outputId": "bae79548-bceb-4c31-855c-dfc176f6ab08"
},
"execution_count": 85,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"(Matrix(MatrixKind.MaxPlus, [[0, 1, -2147483648, 0], [-2147483648, 1, 0, -1], [-2147483648, -2147483648, -2147483648, -2147483648], [-2147483648, -2147483648, -2147483648, -2147483648]]),\n",
" Matrix(MatrixKind.MaxPlus, [[1, 0, 0, -1], [-2147483648, -2147483648, -2147483648, 0], [-2147483648, -2147483648, 0, -2147483648], [-2147483648, -2147483648, -2147483648, 1]]))"
]
},
"metadata": {},
"execution_count": 85
}
]
},
{
"cell_type": "code",
"source": [
"A * B * A # Not what's written in the paper"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "3bduIQ9LnDX4",
"outputId": "d2483d41-76f4-4732-8f5b-66e270131980"
},
"execution_count": 86,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"Matrix(MatrixKind.MaxPlus, [[1, 2, 0, 1], [-2147483648, -2147483648, -2147483648, -2147483648], [-2147483648, -2147483648, -2147483648, -2147483648], [-2147483648, -2147483648, -2147483648, -2147483648]])"
]
},
"metadata": {},
"execution_count": 86
}
]
},
{
"cell_type": "code",
"source": [
"B * A"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "w5XMlqVmnEwT",
"outputId": "47a37fde-7318-4301-9a8b-6f21ad273f2c"
},
"execution_count": 87,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"Matrix(MatrixKind.MaxPlus, [[1, 2, 0, 1], [-2147483648, -2147483648, -2147483648, -2147483648], [-2147483648, -2147483648, -2147483648, -2147483648], [-2147483648, -2147483648, -2147483648, -2147483648]])"
]
},
"metadata": {},
"execution_count": 87
}
]
},
{
"cell_type": "code",
"source": [
"B * A * B"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "SseONBIEvI4u",
"outputId": "ed05c554-3c3e-4543-e5ce-347eeed14608"
},
"execution_count": 88,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"Matrix(MatrixKind.MaxPlus, [[2, 1, 1, 2], [-2147483648, -2147483648, -2147483648, -2147483648], [-2147483648, -2147483648, -2147483648, -2147483648], [-2147483648, -2147483648, -2147483648, -2147483648]])"
]
},
"metadata": {},
"execution_count": 88
}
]
},
{
"cell_type": "code",
"source": [
"alpha, beta, gamma = 3, 2, 1\n",
"pow(B * A, alpha) * pow(A, beta) * pow(B, gamma), Matrix(MatrixKind.MaxPlus, \n",
"[[- alpha - gamma, -alpha - gamma + 1, - alpha + beta + 1, - alpha + beta + gamma + 1], \n",
" [NEGATIVE_INFINITY] * 4,\n",
" [NEGATIVE_INFINITY] * 4, \n",
" [NEGATIVE_INFINITY] * 4])\n"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "TmLhVG_pnSCn",
"outputId": "9c51384e-1e45-4bd8-a3c8-a79677e298a1"
},
"execution_count": 91,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"(Matrix(MatrixKind.MaxPlus, [[4, 3, 5, 6], [-2147483648, -2147483648, -2147483648, -2147483648], [-2147483648, -2147483648, -2147483648, -2147483648], [-2147483648, -2147483648, -2147483648, -2147483648]]),\n",
" Matrix(MatrixKind.MaxPlus, [[-4, -3, 0, 1], [-2147483648, -2147483648, -2147483648, -2147483648], [-2147483648, -2147483648, -2147483648, -2147483648], [-2147483648, -2147483648, -2147483648, -2147483648]]))"
]
},
"metadata": {},
"execution_count": 91
}
]
},
{
"cell_type": "markdown",
"source": [
"Lemma 3.2 (TODO)"
],
"metadata": {
"id": "W8R8T8z3wYk8"
}
},
{
"cell_type": "code",
"source": [],
"metadata": {
"id": "h_spORaLomjf"
},
"execution_count": null,
"outputs": []
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment