Mathematics

10:00 AM

how do I describe the finite subsequence?

given the property I stated

Hi :-) Has anyone ever seen some integrals like \int_{\R^n} \nabla u \cdot (\Delta u I - D^2 u) D^2u \nabla u dx for a compactly supported smooth function u? I know that this is zero if n = 1 or n = 2, and expect that this has a sign for higher dimensions.

Astyx

Are you sure there is a greatest subsequence ? Consider $(1,3,2,4)$. Then you have both $(1,2,4)$ and $(1,3,4)$

user8469759

it's not unique but there's one...

trivially as base case

a finite subsequence of size 1

is the element itself

you can consider it as valid

so for each sequence there's a finite subsequence

Astyx

Well define for instance $A = \{v\text{ subsequences of }u\mid v \text{ is increasing}\}$ and take an element of $A$ of maximal length

Alessandro Codenotti

@user8469759 isn't this always true by definition?

user8469759

10:05 AM

what is true?

that there's always a subsequence with that property?

Alessandro Codenotti

$i<j\implies a_i<a_j$ for all elements

That's how you defined the order

user8469759

yes sorry, drop that order

I was trying to say "consider that set as ordered"

not monotonic

and the order would have given by the indices

from that set I'd like to describe a subset that specifically has the monotonicity as property

that's what I meant

I stated wrongly the problem

Alessandro Codenotti

ok, so what you want is a maximal increasing subsequence of a given sequence

user8469759

yes just the description, I know there's an algorithim to find such a subsequence

Astyx

Isn't what I said good enough ?

user8469759

10:11 AM

no because I'm trying to formalize a recursive equation that usually is kind of given

to solve that problem

Astyx

I don't get it

user8469759

what don't you get?

what I want to do? what's the problem? what's the purpose?

Astyx

I don't understand why what I said is not sufficient

user8469759

you're description is fine, but I don't get how can use it to derive a recursive expression

for the lenght

of the sequence

that has miximum length

Astyx

Oh, you mean you want an algorithm that finds such a sequence ?

user8469759

10:17 AM

Not exactly I want to derive the recursive expression that leads to that algorithm

Astyx

Oh this is a classic, give me a minute

user8469759

because It's a sample problem of a more general class and understanding this simple problem entirely would help a lot

Astyx

It's dynamic programming right ?

user8469759

yeah, you got it

Astyx

Say your sequence is $u^{n} = (a_1, \dots, a_n)$

user8469759

10:20 AM

yes

Astyx

To compute the largest subsequence of $u^{n+1}$, define $v = (a_{n+1})$

Then look at all the sequences $u^{k}$ such that $a_k \le a_{n+1}$

And if the sequence $u^{k} :: a_{n+1}$ is longer than $v$, replace $v = u^k::a_{n+1}$

($::$ denotes concatenation)

user8469759

sorry I don't get it

you have u^n given

and that represents my problem

why would I want to compute the largest subsequence of $u^{n+1}$?

Astyx

You have $u^1, \dots, u^k$ given

Computing the largest subsequence of $u^1$ is trivial

Once you have the largest subsequence of $u^1$, you can compute the largest subsequence of $u^2$

user8469759

but isn't u^2 given?

I don't get your notation

Astyx

Sorry, is it better now ?

user8469759

10:25 AM

can you start over?

please

Astyx

The idea is to look at the largest subsequence of $u^k$ ending with $a_k$ for every $k$

Recursively

user8469759

ok

so your original set is like

$u = (a_1,...,a_n)$

sorry, I meant sequence

and you define $u^k$ as the prefix of length $k$ of $u$

is that right?

Astyx

Yes

user8469759

ok

please go ahead

Astyx

Now for a certain $k$, to compute the largest subsequence of $u^{k+1}$ ending with $a_{k+1}$, you check all the largest subsequences of $u^1,\dots, u^k$ ending with $a_1,\dots a_k$ respectively such that $a_i \le a_k$

Debashish

10:29 AM

HI...interrupting in between (sorry)...I am currently reading "mathematical circles Russian experience". For me, in this book, some of the topics are too trivial and some are interesting and difficult. Overall enjoyable. Could you people suggest more similar books? Thanks !!

user8469759

@astyx ok

Abdullah UYU

@Astyx , I have just read your solution. I am so inspired. just wow!

Astyx

@user8469759 So if you let $v^k$ be the largest subsequence of $u^k$ ending with $a_k$, then you have that $v^{k+1}$ is the longest sequence of $$\{v_i::a_{k+1}\mid a_i\le a_{k+1} \text{ and } 1\le i\le k\}$$

(where $::$ still denotes concatenation)

user8469759

My first attempt

on this problem

o no sorry

Astyx

Wait, do you agree with this first ?

user8469759

10:34 AM

that first attempt was related to another problem

I'm reading

yes, it seems it makes sense

Astyx

So you can compute $v^{k+1}$ from $v^1,\dots, v^k$, which gives your recursion "formula"

user8469759

but should the complexity that comes out from this solution

be quadratic?

Astyx

And you're interrested in the longest sequence among $v^1,\dots, v^n$

Yes it's quadratic unless I'm mistaken

user8469759

ok, because this problems drives me crazy for what concerns complexity

Astyx

Since to compute $v^k$ you have $k$ bunch of operations to do

bunches*

user8469759

10:49 AM

thanks for your help

Astyx

10:59 AM

Glad I could help

Alex K Chen

Are there any chatroom for toying with $LaTeX$ $FeAtUrEs ?$

Danu

@Semiclassical Do you know any books on Riemann surfaces that could be useful for analysts (I mean Schrödinger equation type analysts) who need to work with more complex analysis/branch cut type stuff?

Akiva Weinberger

I suppose the sandbox counts?

But you can do that here if you want

Alex K Chen

$\boldsymbol{I \; am \; asking \; this \; because} \mathfrak{Latex \;\; and \; Chat \; often \; mix \; to \; produce } \texttt{Interesting and funny}\mathbf{Results}$

@AkivaWeinberger No, okay, I will do that there.

Danu

@TedShifrin ^^^^^ any suggestions?

Akiva Weinberger

11:07 AM

Turn $\rm right\atop left$

Wait, no, turn $\rm left\atop right$

Alex K Chen

@AkivaWeinberger $\mathfrak{You \; do \; hockey \; pockey \; and \; turn \; yourself \; around}$

($\mathbf{I \; am \; joking, \; of \; course}$)

Well, anybody up for a game of sprouts/Gale ?

Abdullah UYU