Legumes and Potatoes are Certainly P-A-L-E-O

Tubers are as Ancient as Bipedalism

The Paleolithic Age started ~2.6 mya and extended to only 12,000 years ago. The last Homo neanderthalensis existed up to ~25,000 years ago, and in fact their DNA exists in nearly all of us. One of our ancient human ancestors, Australopithecine boisei (formerly known as Paranthropus boisei), did not eat the stiff and hard textured nuts that their tough jaws and mean bite alluded to, but instead appeared to consume a diet rich in soft sedge tubers (including tigernuts) that grew buried in the soft land near waterways and shorelines. He had nickname, Nutcracker man. And lived with great longevity from 2.4 mya to 1.4 mya, impressively longer (that I'm aware of) than any other hominin ancestor that humans have had. Nutcracker man indeed started our human evolution with increasingly larger brain sizes during his 1 million year reign and likely planted the seeds for yet even larger brain sizes in 'subsequent prototypes' in Homo.

The moors, peatlands, and marshlands of Scotland and northern Europe were very similiar to the Paleo 'nutriscape' and terrain during the transition from Ice Ages to mega C4 sedge and grasslands. I suspect our ancestors consumed a pretty heady diet of plant fiber and starch because sedge tubers/corms/rhizomes (including tiger nuts), cattail bulbs, water chestnuts, wild carrots, yams, and other starchy roots were common underground storage organs (USOs).  Tubers like tigernuts and other underground sedge roots had a different, more evolved form of photosynthesis that required less molecules of water and selected during the shift in weather from moist and aquatic to dry grasslands. The final electron donor switched from water which had become intermittently scarce to sugar/starch molecules. During intermittent freezing and warm periods, sugar and starch additionally served another role as a buffer from cold trauma and frost.

Tigernuts and sedges were offspring of the new C4 photosynthetic plants and grew plentifully. Papyrus is also an example of a sedge. C4 plants and roots produced a radiation signal that was found in great amounts in C13/C14 isotope density studies from enamel and Nutcracker remains from 1-2 mya. Being sweet, starchy and high in protein, it was no wonder that our ancient ancestor found sedge tubers and tigernuts so delightful to exploit.

In the Paleolithic Age, both Homo and Australopithecine fed themselves well enough to not only survive the Ice Ages, predators, pathogens and newly discovered bipedalism, but also to grow a higher capacity cranium. One of the leading theories for this is digestible carbohydrates. Without complex carbohydrates and high fiber starches from USOs it is unlikely that fruit and honey alone would have exploded the process of encephalization. For tens of millions of years our primate cousins had failed to forge larger brains as frugivores. What changed? Researchers Brown et al reviewed the diet of our primal forefathers and noted they likely consumed "high carbohydrate sources including plants particularly those with underground storage organs (USOs) such as reed mace (Typha), common reed (Phragmites), water chestnut (Trapa natans) and yellow water lily (Nuphar lutea). USOs have repeatedly been implicated in hominin evolution and particularly encephalisation and bipedalism in the Africa [83], [72], [84]–[85] although this has been challenged [86]."

USOs provide valuable nutrients for brain fuel: zinc, magnesium, carbohydrates, sucrose, vitamin C (one serving, almost 50% of RDA), and protein. In terms of the brain-gut evolution, digging for tubers also tied our ancestors to the ground in more ways than the descent from the arboreal heavens to terra firma living and bipedalism. SBO probiotics (soil-based organisms) clung to every new bite of dirt-covered tubers. For tree hugging primates, the new terrain brought not only fresh and novel food, but also broad exposures to a whole new world of micro-organisms. Remember, diet (dirt lol) is the biggest driver of the microbiota and evolution of the gut. Transformation of gut and brain occurred simultaneously I believe. Our herbivore colon shrunk as our brains exponentially expanded... or even doubled: gut and cranium.

AG Brown et al, 2013
Site Distribution at the Edge of the Palaeolithic World: A Nutritional Niche Approach

This paper presents data from the English Channel area of Britain and Northern France on the spatial distribution of Lower to early Middle Palaeolithic pre-MIS5 interglacial sites which are used to test the contention that the pattern of the richest sites is a real archaeological distribution and not of taphonomic origin. These sites show a marked concentration in the middle-lower reaches of river valleys with most being upstream of, but close to, estimated interglacial tidal limits. A plant and animal database derived from Middle-Late Pleistocene sites in the region is used to estimate the potentially edible foods and their distribution in the typically undulating landscape of the region. This is then converted into the potential availability of macronutrients (proteins, carbohydrates, fats) and selected micronutrients. The floodplain is shown to be the optimum location in the nutritional landscape (nutriscape). In addition to both absolute and seasonal macronutrient advantages the floodplains could have provided foods rich in key micronutrients, which are linked to better health, the maintenance of fertility and minimization of infant mortality. Such places may have been seen as ‘good (or healthy) places’ explaining the high number of artefacts accumulated by repeated visitation over long periods of time and possible occupation. The distribution of these sites reflects the richest aquatic and wetland successional habitats along valley floors. Such locations would have provided foods rich in a wide range of nutrients, importantly including those in short supply at these latitudes. When combined with other benefits, the high nutrient diversity made these locations the optimal niche in northwest European mixed temperate woodland environments. It is argued here that the use of these nutritionally advantageous locations as nodal or central points facilitated a healthy variant of the Palaeolithic diet which permitted habitation at the edge of these hominins’ range.

Paleo People Loved Legumes

Neanderthals probably didn't do a fantastic job with legumes and small grain grasses because now they are extinct. It took a few dozen thousands of years...a slow demise, if that one of the reasons for their demise. During the latter portion of the Paleolithic, smarter hominids came along and figured out how to soak and cook legumes and SGGs. Food processing easily removes toxins and transforms them toxic, hard bumps of plant seeds into edible and delicious sources of starch, fiber, fat and protein.

Wrangtham et al in 'The Evolution of Hominin Diets' (2009) discusses the use of legumes in the end of Paleolithic Age, before the advent of agriculture. Plant evidence doesn't survive time well. What was unearthed was corroborated at a variety of sites widely distributed throughout Europe and Eurasia.

Legumes may be questionably Paleo® but they are unquestionably bionic for the gut microbiota and fuels the most important populations throughout the entire length of gut. The special fibers in legumes are unequaled when it comes to the combination of both RS3 and non-starch polysaccharides. Instead of raising blood sugars, legumes are low glycemic index meaning they impact insulin minimally or in fact lower it. Legumes have no dearth of clinical human trials that demonstrate its value for significantly lowering cancer, inflammation, insulin resistance, blood sugars, and gastrointestinal disorders.

Wrangtham et al in 'The Evolution of Hominin Diets' (2009)
"The richest food plant assemblage of Mousterian date, at
Kebara Cave in Israel, is dominated by a legume seeds of a
range of species, the form of some of which might suggest
collection while underripe (Lev et al., 2005). Towards the endof the Paleolithic, legume finds are scattered across Europe,
for example the pea and bitter vetch at Öküzini, Turkey; lentil
at Konispol cave, Albania; and vetches and other legumes at
Santa Maira, Alacant, Spain (Baales et al., 2002). Another
rich example of pre-agricultural legume foragers comes from
Hallam Cemi in Turkish Anatolia (Savard et al., 2006).



New Environments and New Plant
Strategies

Monocot stems and legume pods may have provided a significant mass of plant foods during the expansion into thel ower latitudes of Eurasia, where a vast array of yams and
legumes have emerged in the modern human food web as
domesticated plants. Moving further northwards still, these
kinds of resources diminish significantly, both in diversity
and in biomass availability. The quest for plant foods will
have presented an increasing challenge.
The cooler northern vegetation stands would have been
characterised by a range of open biomes including “arctic
steppe” (Cwynar and Ritchie, 1980; Zazula et al., 2003)
and closed vegetations characterised by woody dicots and
coniferous trees. Woody dicots are reasonably rich in edible
nuts, kernels, and fruits and, in certain families, edible roots
and tubers. As mentioned above, the lower the biological
productivity, the greater evolutionary pressure to protects eeds and storage organs from predation, and so it is generally
true that, especially as they move northwards, human
feeders are presented with a more complex “landscape of
toxicity” by dicots than tends to be the case with monocots,
particularly in the context of the seeds and tubers upon whicht he plant itself relies to cross the non-growing season. The  kind of transferable ecological 
knowledge that allowed feedersto move from one monocot to another in more southerly
biomes is not directly transferable to the dicots in northerly
biomes.