# Questions tagged [computation]

The computation tag has no usage guidance.

30
questions

**0**

votes

**0**answers

53 views

### Quick ways to compute transition matrices for classical symmetric function bases

I am trying to implement quick algorithms for computing the transition matrices
involving the monomial, power-sum, elementary, complete homogeneous and Schur polynomials.
There are several relations ...

**4**

votes

**0**answers

63 views

### Amortized complexity of P

Let $P$ be the class of all polynomial time computable functions from $\{0,1\}^*\rightarrow \{0,1\}$. For any $f\in P$, define function $f^A:\mathbb{N}\rightarrow \{0,1\}^*$ by
$$f^A(n)=(f(x_1),\cdots,...

**4**

votes

**1**answer

107 views

### Algorithm to construct basis for Kac-Moody algebra

Suppose I have a Kac-Moody algebra (maybe even Borcherds-Kac-Moody) $\mathfrak{g}$ with symmetric cartan matrix $A$. Let the simple roots be $e_{\alpha_i}$ for $i = 1, \ldots n$.
I know there is ...

**0**

votes

**0**answers

22 views

### Explicit computation of spectrum of some infinite trees

This is probably more of a computational matter, but on Mathematica StackExchange they closed my question, so I try and ask here as well.
I would like to compute the spectrum of some infinite trees ...

**0**

votes

**1**answer

609 views

### Conjecture that relates matrix systems with some specific functions as solution sets

what is written below is a conjecture that I posed , and I ask for a proof or a disproof of it .I have checked the conjecture from $n$=$1$ up to $n$=$10$ using Matlab, and all results were in ...

**1**

vote

**1**answer

141 views

### Errors in Waksman's Solution to Cellular Automaton Firing Squad Problem?

Recently, a student and I have been working through Waksman's paper ``An Optimum Solution to the Firing Squad Synchronization Problem.'' The paper claims that for any value of $n$, the proposed ...

**5**

votes

**0**answers

68 views

### Numerical and computational approaches to limit cycle theory

I am searching for a big list of papers or researches devoted to limit cycles of planar polynomial vector fields based on a computational and numerical approach.
I would like to ask ...

**3**

votes

**0**answers

157 views

### curve blow ups of toric Fano $3$-folds

Suppose $X$ is a smooth toric Fano $3$-fold, and $D$ is a torus invariant divisor corresponding to a face of the polytope associated to $X$. I would like to search for (smooth) curves $C \subset D$, ...

**4**

votes

**1**answer

612 views

### Conjecture on palindromic numbers

The conjecture is as follows:
Let $n\in\mathbb{N}\setminus\{1\}$. Define $a(n)=2^n+1$ and the set:
$$S(n) = \{ (a(n)^m+1)/2\ :\ m\in \mathbb{N}_0\}.$$
Then for all $c\in\mathbb{N}$, the number $(a(n)...

**8**

votes

**1**answer

428 views

### simple conjecture on palindromes in base 10 [closed]

The conjecture says that for any a, b belong to the the set of non-negative integers ($a$ and $b$ are not necessarily distinct), taking any natural value of $c$; we have always that $$(10^c-1) \cdot \...

**1**

vote

**1**answer

570 views

### Conjecture that relates matrix systems with some polynomials of integer coefficients as solution sets

Assume $x$ is a variable belongs to $\mathbb R \setminus \{ 0,-1,+1 \}$ and consider for all $i, j \in \mathbb N$,
$$a(i,j) = \frac{(x^{i+1} + 1)^{j-1} + (x-1)}{x}$$
then for all $n \in \mathbb N$ the ...

**7**

votes

**1**answer

339 views

### What Turing degree would allow you to “compute” the axioms of ZFC in some countable model of ZFC?

It is established in this post that you there is no computable model of ZFC, yet it can be computed in by a PA-degree oracle machine. Note that when we see "compute a model", we just mean that ...

**0**

votes

**0**answers

124 views

### Computer algebra programs for dummies

In the way of my investigations I have encounter the following computational problem: I have a system of 5 algebraic equations and I want to eliminate 4 of them. I also need to do a functional ...

**6**

votes

**1**answer

237 views

### Problem on triangles

Let $T\subset \mathbb{R}^2$ be any triangle and $T^t$ a deformation of $T$. Call $l_1,l_2,l_3$ the squares of the lengths of the sides of $T$ and $l_1^t,l_2^t,l_3^t$ the squares of the lengths of the ...

**6**

votes

**1**answer

418 views

### Algorithm to compute Matrix Sign Rank?

The (generalised) sign-rank of a (generalised) sign pattern $S\in \{+,-,0\}^{n\times m}$
is the minimum rank of all matrices with the same sign pattern, i.e.
$$
\min\left\{\operatorname{rank}(M)\ :\ M\...

**8**

votes

**2**answers

286 views

### Curves embedding in plane

Given two closed simple(no self-intersection point) curves $C_1,C_2$ in the plane $\mathbb R^2$, is there a good way to judge whether one curve can be embedded inside the other one, here embedding ...

**6**

votes

**2**answers

940 views

### Complexity of Turing Machine behavior

If one looks at the code for a Turing Machine (TM) with
$q$ states and, let's say, $2$ symbols, they all look
pretty much the same:
A list of $5$-tuples:
$$
< state, symbol{-}read, symbol{-}to{-}...

**19**

votes

**0**answers

461 views

### Checking Mertens and the like in less than linear time or less than $\sqrt{x}$ space

Say you want to check that $|\sum_{n\leq x} \mu(n)|\leq \sqrt{x}$ for all
$x\leq X$. (I am actually interested in checking that $\sum_{n\leq x} \mu(n)/n|\leq c/\sqrt{x}$, where $c$ is a constant, and ...

**5**

votes

**0**answers

90 views

### Efficiently computing all equivariant maps between two $GL_n$-representations

This is sort of a strange question; if it's not appropriate for MathOverflow I apologize in advance.
I'm in a situation where I'd like to be able to give a computer two $GL_n$ representations $V$ and ...

**1**

vote

**1**answer

192 views

### Polygonal Mersenne numbers [closed]

I posted the same question on Math SE since this one got put on hold.
Link to Math SE question:Polygonal Mersenne numbers
Polygonal numbers are of the form $\cfrac {n^2(s-2)-n(s-4)}{2}$, where $s$ ...

**-1**

votes

**1**answer

85 views

### How to generate computational data in graph theory?

For a given number of nodes how many non-isomorphic graphs are available? Might be this is an open problem. For less number of vertices some computational statistics available.
I want to get all non-...

**0**

votes

**0**answers

76 views

### Bits of precision matrix reconstruction

We have a real rank $r$ matrix $M\in\{0,1\}^{n\times n}$.
Suppose we have diagonalized using $LMR=D$.
I want to recover a real matrix $\widetilde{M}$ such that maximum absolute entry of $\widetilde{...

**3**

votes

**2**answers

313 views

### efficiently checking that a field extension is Galois

Let $K \subset L$ be an algebraic extension of fields finitely presented over a prime field or over an algebraically closed field. Is there an efficient procedure to check that $L/K$ is Galois? To ...

**0**

votes

**1**answer

154 views

### Refutation of $A \land \lnot\lnot\lnot A$ by resolution [closed]

$ A \land \lnot\lnot\lnot A $ this is a very simple example. Resolution is refutation complete. So it should be able to refute this formula. However, I don't see how would it do that without using ...

**3**

votes

**0**answers

106 views

### Weak randomness relative to finite-state machines

Is there a nice example of a sequence that looks random to any predictor whose predictions use a finite-state machine?
More precisely, consider a finite-state machine $M$ with input alphabet {0,1} ...

**4**

votes

**5**answers

332 views

### procedure-based (as opposed to definition-based) concepts

Euler's work on divergent series was guided by computational procedures, rather than any definition of the "value" of such a series. E.g., he was happy to have half a dozen procedures that indicated ...

**0**

votes

**3**answers

442 views

### System of quadratic equations with 18 unknown

So I want to solve for a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r which satisfy the following system of equations: ( I only need positive integer (or 0) solution)
a g + c h + b i + g j + i ...

**70**

votes

**16**answers

4k views

### Important open problems that have already been reduced to a finite but infeasible amount of computation

Most open problems, when formalized, naturally involve quantification over infinite sets, thereby obviating the possibility, even in principle, of "just putting it on a computer."
Some questions (e.g....

**16**

votes

**3**answers

1k views

### What to do when your research runs into a computationally challenging problem?

Occasionally, but more frequently lately, I would like to perform some hard computations. As an example, yesterday the following question came up:
What is the projective dimension of the edge ideal ...

**3**

votes

**1**answer

555 views

### Efficiently computing with pullbacks and pushouts

Often when computing in category theory, one has to show that some square is cartesian. Depending on the number of maps involved, and their arrangement, it's somewhat difficult to write down exactly ...