Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines? Question: Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?

Background: I recently stumbled upon the dissertation &quot;Computational complexity of multitape Turning machines and Random Access Machines&quot; by Takumi Kasai (see here: https://repository.kulib.kyoto-u.ac.jp/dspace/handle/2433/86527).
As far as I can tell, the author shows that there exists a function $g$ such that $g$ can be computed in $O(n)$ time by RAM machines, but cannot be computed in $O(n^{2-\varepsilon})$ time by Multitape Turing machines for all $\varepsilon &gt; 0$.
Can this result be extended to deciding languages (instead of computing functions)?  In other words, can we prove that there is a language decidable in $O(n)$ time by RAM machines that cannot be decided in $O(n^{2-\varepsilon})$ time by Multitape Turing machines for all $\varepsilon &gt; 0$?
It depends on the precise definition of RAM being used, but (for most reasonable definitions of RAMs) this would also imply that SAT is not solvable in $O(n^{2-e})$ time by multitape TMs, a longstanding open problem.
The reason is that there is a very efficient reduction from linear time on RAMs to SAT (in general, nondeterministic quasi linear time on RAMs is the same as nondeterministic quasi linear time on multitape TMs.)
I have never seen the above reference before, and I would be skeptical if it never appeared in a journal or conference, but it could be worth checking to see if it implies a SAT lower bound as well. Interesting find!

UPDATE: I looked at the paper at your link above briefly this morning. The claimed hard function is a complicated partial match query problem. Essentially there is a notion of a &quot;string pattern&quot; and one is given a bunch of binary strings and asked to determine which strings fit the pattern (and which don't). Let me write out the definition of the function, as I understand it. I will use different symbols and terminology to try to make the definition easier to understand.
The set of &quot;string templates&quot; (the author's $U$, Definition 5.1) is a set of strings over $\{0,1,end,branch\}$, defined recursively:

$end \in U$
$\alpha \in U$ implies $0\alpha, 1\alpha \in U$
$\alpha, \beta \in U$ implies $branch~ \alpha \beta \in U$.
Note that every string ends in an $end$ symbol. The $branch$ is used to denote a possible choice in the match: either $\alpha$ can be matched as a partial string, or $\beta$, and $end$ is used at the end of $\alpha$ to signal where $\alpha$ ends and $\beta$ begins.

We say that a binary string $x$ &quot;matches&quot; a string template $\alpha \in U$ (the author's Definition 5.2) if $x$ is in the set $\phi(\alpha)$, recursively defined as:

$\phi(end) = \epsilon$ ($end$ symbols are removed)
$\phi(b\alpha) = b \phi(\alpha)$ for $b \in \{0,1\}$ (normal string matching)
$\phi(branch~ \alpha \beta) = 0\phi(\alpha) \cup 1 \phi(\beta)$, for $\alpha,\beta \in U$.
The third condition is the main one here: the author intends for us to find the $end$ symbol that &quot;matches up&quot; with the first $branch$ symbol, and partition $\alpha$ and $\beta$ according to that. Then, depending on whether the next symbol of $x$ is $0$ or $1$, the next piece of $x$ should either partial-match to $\alpha$ or partial-match to $\beta$.

It should be analogous to think of an $\alpha$ as an encoding of a (rooted) binary tree (each node has at most two children), where we label each edge of the tree by $0$ or $1$, and we say that a string $x$ matches the tree if there's some root-to-leaf path whose concatenated symbols are exactly $x$.
Anyway, the final presumed hard function $g$ (Definition 5.2) is:
Given a string template $\alpha \in U$ and given binary strings $x_1,\ldots,x_k$ (where each string is separated by a new symbol) output $k$ bits indicating which $x_i$'s match the template $\alpha$.
If this was a &quot;normal&quot; partial match query problem (e.g. with strings over $\{0,1,\star\}$, then it would be easily computed in $O(n)$ time on a multitape Turing machine, even one that just reads its input in one direction. I don't see  why computing multiple queries on a binary search tree should take super-linear time for a multitape Turing machine. (I don't see why following $K$ paths down a binary tree of description size $N$ should take more than $(N+K) \cdot poly(\log(KN))$ time.) And the fact that it didn't appear in a major conference or a major journal makes me very suspicious. (It does appear in a journal: https://www.ems-ph.org/journals/show_pdf.php?issn=0034-5318&amp;vol=13&amp;iss=2&amp;rank=5) But I didn't spend more than an hour looking at this!

FINAL UPDATE: Brynmor Chapman looked at this paper more closely, and observed the proof only gives a lower bound for the &quot;on line&quot; version of the function, where the query for each binary string $x_i$ (as described above) must be answered (the TM must output a bit) before the TM is allowed to read the next binary string $x_{i+1}$. This a data structure lower bound for TMs, which is much easier to prove given the 1-dimensional nature of TM tapes. That is, the lower bound proved is much weaker than what is claimed: that there is a function $g$ computable in linear time on RAMs which requires nearly quadratic time on a multi-tape Turing machine. As far as I know, that claim remains open.